[pyar] Buscando la subcadena comun mas larga

[Anthony Lenton]

On Tue, Jul 13, 2010 at 2:37 PM, Daniel Moisset <dmoisset en machinalis.com> wrote:
> 2010/7/13 Anthony Lenton <antoniolenton en gmail.com>:
>> 2010/7/13 Lucas <rollbak en gmail.com>:
>>> Tambien podrias probar con el SequenceMatcher de difflib [0]
>>>
>>> [0] http://docs.python.org/library/difflib.html#sequencematcher-objects
>
> para, difflib hace longest common subsequence, y por lo que yo lei
> querías longest common substring.
>
> O sea, si s1 = "xcxaxsxa" y s2="ycyaysya", el longest common
> subsequence es casa, y el longest common substring es "c". Cual es el
> que buscás?

Longest common substring es lo que andaba buscando.  Longest common
subsequence capaz también me sirve, pero ese es otro tema.

Por otro lado, parece que difflib sabe calcular LCSubstring:

>>> a = "So long, and thanks for all the fish"
>>> b = "Don't panic"
>>> s = difflib.SequenceMatcher(None, a, b)
>>> s.find_longest_match(0, len(a), 0, len(b))
Match(a=4, b=1, size=2)

Acá dice que el LCSubstring es "on", cuando LCSubsequence sería
"onan".  O también,

>>> a = "xcxaxsxa"
>>> b = "ycyaysya"
>>> s = difflib.SequenceMatcher(None, a, b)
>>> s.find_longest_match(0, len(a), 0, len(b))
Match(a=1, b=1, size=1)

"c", como queríamos.  Ahora, LCSubsequence puede estar interesante también :)

-- 
Anthony Lenton