[plt-scheme] longest common substring!

From: Daniel Yoo (dyoo at cs.wpi.edu)
Date: Mon Apr 2 17:57:06 EDT 2007

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.


Posted on the users mailing list.