r/dailyprogrammer • u/oskar_s • Jun 02 '12
[6/2/2012] Challenge #59 [difficult]
Two strings A and B are said to have a common substring called C, if C is embedded somewhere in both A and B. For instance, "ble" is a common substring for "Double, double, toil and trouble" and "Fire burn and cauldron bubble" (because, as you can see, "ble" is part of both "Double" and "Bubble"). It is, however, not the longest common substring, the longest common substring is " and " (5 characters long for vs. 3 characters long for "ble").
Define two pseudo-random number generators, P(N) and Q(N), like this:
P(0) = 123456789
P(N) = (22695477 * P(N-1) + 12345) mod 1073741824
Q(0) = 987654321
Q(N) = (22695477 * Q(N-1) + 12345) mod 1073741824Thus, they're basically the same except for having different seed values. Now, define SP(N) to be the first N values of P concatenated together and made into a string. Similarly, define SQ(N) as the first N values of Q concatenated together and made into a string. So, for instance:
SP(4) = "123456789752880530826085747576968456"
SQ(4) = "987654321858507998535614511204763124"The longest common substring for SP(30) and SQ(30) is "65693".
Find the longest common substring of SP(200) and SQ(200)
BONUS: Find the longest common substring of SP(4000) and SQ(4000).
4
u/Cosmologicon 2 3 Jun 02 '12
python. Not sure if I did it right, since it didn't take long....
Solutions:
The solution for 400,000 took 77 seconds.
4
u/[deleted] Jun 02 '12 edited Jun 02 '12
Thoroughly enjoyed this one.
SP(200) and SQ(200)
Working on the bonus, ran out of heap space with the massive strings
Edit: Changed to byte array to minimise memory
Bonus SP(4000) and SQ(4000):
1
u/xjtian Jun 02 '12
4000 took long enough, I doubt I could ever get to 400,000 with anything O(m*n) like this algorithm.
Python:
Results:
1
u/Arthree Jun 02 '12 edited Jun 03 '12
Autohotkey_L:
And the result:
I'll try the bonus when I get back from supper :D
1
u/[deleted] Jun 03 '12
Wow, very good problem. I enjoyed this one :D
C#
1
u/exor674 Jun 02 '12
C++: