[pyar] Buscando la subcadena comun mas larga

[Anthony Lenton]

2010/7/13 Lucas <rollbak en gmail.com>:
> Buenas,
>
> No probaste usar Levenshtein? En [0] hay un modulo en c.
>
> [0] http://code.google.com/p/pylevenshtein/
>

Sip, en realidad con
http://www.michael-noll.com/wiki/Python-Levenshtein porque anda un
poquito más rápido y además viene en Ubuntu.
Es bastante distinto a LCS, pero como medida de distancia es interesante.
Es *bastante* más rápido que LCS (~1 minuto para la corrida entera),
por más que los dos son O(m*n) supuestamente, supongo que en parte
porque es una extensión de C, en parte porque las constantes son más
lindas, y en parte porque es código de producción y no un post de
alguien en un blog :)

El tema es que, para lo que quiero, y hasta donde medí, LCS me anda un
poco mejor.

-- 
Anthony Lenton