[plt-scheme] longest common substring!
Hi everyone,
I finally cooked up a direct application of suffix trees to solving the
longest common substring problem. I don't know why in the world I omitted
this.
http://hashcollision.org/svn/repos/projects/plt-misc/suffixtree/longest-common-substring.ss
For example:
> (longest-common-substring "1010101" "11101" "00000100000")
"01"
The cool thing is that this should be computed in time linear to the
length of all the strings. I'll probably have to profile it to make sure
it really is doing this computation in linear time, but thought it might
interest people.
(I can see this being generalized to be able to find longest repetitions
between source code fragments...)
I'll include it in the next release of the suffixtree package on PLaneT.