Aus Abschnitt 15.2 der Perlenprogrammierung

Die C-Codes können hier eingesehen werden:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

Wenn ich es mit dem Suffix-Array in Python implementiere:

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

Ich fand es sehr langsam für dieidx.sort Schritt. Ich denke, es ist langsam, weil Python den Teilstring nach Wert anstatt nach Zeiger übergeben muss (wie die C-Codes oben).

Die getestete Datei kann von heruntergeladen werdenHier

Die C-Codes benötigen zum Beenden nur 0,3 Sekunden.

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

Aber für Python-Codes endet es nie auf meinem Computer (ich habe 10 Minuten gewartet und es beendet)

Hat jemand Ideen, wie man die Codes effizienter macht? (Zum Beispiel weniger als 10 Sekunden)