Из раздела 15.2 «Программирование жемчуга»

Коды С можно посмотреть здесь:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

Когда я реализую это в Python, используя суффикс-массив:

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

Я нашел это очень медленно дляidx.sort шаг. Я думаю это'медленный, потому что Python должен передавать подстроку по значению, а не по указателю (как код C выше).

Протестированный файл можно скачать сВот

Для кодов С требуется всего 0,3 секунды.

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

Но для кодов Python это никогда не заканчивается на моем компьютере (я ждал 10 минут и убил его)

У кого-нибудь есть идеи, как сделать коды эффективными? (Например, менее 10 секунд)