De la Sección 15.2 de Perlas de Programación.

Los códigos C se pueden ver aquí:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

Cuando lo implemento en Python usando sufijo-array:

example = open("iliad10.txt").read()
def comlen(p, q):
    i = 0
    for x in zip(p, q):
        if x[0] == x[1]:
            i += 1
        else:
            break
    return i

suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:]))  #VERY VERY SLOW

max_len = -1
for i in range(example_len - 1):
    this_len = comlen(example[idx[i]:], example[idx[i+1]:])
    print this_len
    if this_len > max_len:
        max_len = this_len
        maxi = i

Lo encontré muy lento para elidx.sort paso. Creo que es lento porque Python necesita pasar la subcadena por valor en lugar de por puntero (como los códigos C anteriores).

El archivo probado se puede descargar desdeaquí

Los códigos C solo necesitan 0.3 segundos para terminar.

time cat iliad10.txt |./longdup 
On this the rest of the Achaeans with one voice were for
respecting the priest and taking the ransom that he offered; but
not so Agamemnon, who spoke fiercely to him and sent him roughly
away. 

real    0m0.328s
user    0m0.291s
sys 0m0.006s

Pero para los códigos Python, nunca termina en mi computadora (esperé durante 10 minutos y lo maté)

¿Alguien tiene ideas de cómo hacer que los códigos sean eficientes? (Por ejemplo, menos de 10 segundos)