[Haskell-cafe] Re: Memoizing longest-common-subsequence

Mark.Carroll@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/. Benedikt