[Haskell-cafe] Re: Memoizing longest-common-subsequence
beschmi at cloaked.de
Tue Aug 1 10:13:05 EDT 2006
Mark.Carroll at Aetion.com (Mark T.B. Carroll) writes:
> I wanted a longest common subsequence function and a bit of Googling
> failed to turn up a functional one, except for in a scary bit of darcs.
The code in darcs is a translation of the example code in the Eugene Myers
paper mentioned in the comments and the C code in GNU diff. I didn't try
much to simplify it because I first wanted to see how close I could come
to the perfomance of the C code.
> Take this as your cue to point out the much better LCS algorithm that
> already exists in the standard libraries, that I couldn't find. (-:
There is a nice implementation of the Hunt-Szymanski algorithm by
Ian Lynagh at http://urchin.earth.li/darcs/ian/lcs/.
More information about the Haskell-Cafe