[pyar] Buscando la subcadena comun mas larga

[Anthony Lenton]

2010/7/13 Federico Heinz <fheinz en vialibre.org.ar>:
> On 13/07/2010, Ricardo Aráoz wrote:
>> Y no haría nada. La especificación dice que querés saber cuál es el
>> vecino más cercano. Por ejemplo, si tomás "casa1" el vecino más
>> cercano sólo puede ser "casa0" o "casa1000" que son el anterior y
>> el siguiente en la lista.
>
> Me parece que están asumiendo que lo que busca áchuni es el "common
> longest prefix", no "longest common substring". En otras palabras,
> como yo lo entendí, también tiene que poder encontrar que entre los
> strings

Exacto.

Por si faltaban ejemplos, si tuviera una lista así (ya ordenada):

['alabastro', 'apabullar', 'astro', 'aullar', 'pala']

Ningún string queda adyacente al que tiene la subcadena en común más larga.
Si agregaramos todas las rotaciones de los strings a la lista
(indicando de alguna manera cuál era el string original) capaz
funcionaría, pero ya la complejidad se nos fue a O(rrible).

-- 
Anthony Lenton