LCS algorithm

[Alex Martelli]

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.

difflib.py in the standard python library contains that, as well
as much else besides.

>>> import difflib
>>> sm = difflib.SequenceMatcher()
>>> a = 'One by one the guests arrive'
>>> b = 'The guests are coming through'
>>> sm.set_seqs(a, b)
>>> sm.find_longest_match(0, len(a), 0, len(b))
(12, 1, 12)
>>> a[12:12+12]
'he guests ar'
>>> b[1:1+12]
'he guests ar'
>>>


Alex