Overlap Detection in strings, with code
neil.fraser.name
neil.fraser.name
There are other algorithms besides KMP too for this. I'm sure with some thinking on my part the linear time suffix tree algorithms could solve this too off hand.
The startup was doing network compression - put an appliance either side of a WAN link and transparently compress the data inbetween. The core loop of that is examining IP and TCP traffic and determining if you have seen something like that before and how much of a match you have. If there is a match then you can just send the match details to the other side rather than the actual data. Typical compression ratios were 20:1 / 95% - ie you could stuff 20 times as much data through the link.
The standard zip algorithm has a window of 32kb (ie it looks roughly 32kb behind to see if data has been repeated). bzip2 uses 900kb. That is usually less than a second or two on standard WAN links! The founder's algorithm worked over hundreds of megabytes.
(The company name was Peribit Networks - you'll find Wikipedia rather unhelpful.)
With that in mind, it is _obvious_ that there is an algorithm linear in the size of the overlap to compute it. For instance:
def commonOverlapSanely(text1, text2):
right = len(text1)-1
left = 0
maxleft = len(text2)
while left < maxleft and right >= 0:
if text1[right] != text2[left]:
break
right -= 1
left += 1
return left
Instead of using this _very simple_ algorithm, the author employs three different approaches:1. A "naive" version that keeps copying increasingly large portions of the original strings, and checking the whole portion each time. This obviously makes the algorithm quadratic in the size of the overlap, thus leading to very bad performance.
2. The KMP algorithm, that is designed to search for occurrences of a string within another one, disregarding where. This is a silly thing to do because the resulting algorithm is linear in the size of the longest input string, instead of on the size of the actual overlap.
3. An "indexOf" monstruosity, that is so wrong it is even hard to explain. Carefuly inspect the code and cry.
Now, please tell me if I missed something...
I've just run a few naive tests and all three versions on the linked page give the same result on every test, and yours gives different results on some of the tests. In short, your code doesn't work.
So you've missed something.