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

[Benedikt Schmidt]

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/.

Benedikt