[pyar] Buscando la subcadena comun mas larga

[Anthony Lenton]

Buenas!

Ando queriendo que hacer búsquedas de la subcadena común más larga
entre dos strings.  Bueno, en realidad entre todos los pares de una
bolsa de como 1000 strings, por lo que me anda leeento.

Primero probé con algo básico como esto:
  http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python

Viendo que no terminaba más me fijé algo que usar suffix trees y encontré esto:
  http://chipsndips.livejournal.com/2005/12/07/

Que mejora notablemente, pero sigue demorando bastante (15 minutos para todo).

Entonces me preguntaba, alguien conoce alguna extensión en C para
hacer esto más rápido?  O, habrá alguna forma de aprovechar el hecho
de que estoy comparando siempre los mismos strings de a 2, como para
optimizar?

Nos vemos,

--
Anthony Lenton

-- 
Anthony Lenton