LCS algorithm

[David Eppstein]

In article <slrnatbqmn.f8e.mlh at furu.idi.ntnu.no>,
 mlh at furu.idi.ntnu.no (Magnus Lie Hetland) wrote:

> In article <3DCD1A12.4070809 at nospam.net>, Drazen Gemic wrote:
> >Is there an implementation of Largest Common Sequence algorithm
> >in Python ? I am particulary interested in implementation that
> >works for character strings.
> 
> Here is an implementation of Levenshtein distance (edit distance):
> 
> http://hetland.org/python/distance.py
> 
> The two are very similar.

Here's one I coded up the last time I covered this in my algorithms 
class:

http://www.ics.uci.edu/~eppstein/161/python/lcs.py

It works for string input but the output is a list, you'd have to 
convert it back to a string by ''.join(...)

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/