Suffix Array

Wir schauen uns allerdings jetzt eine Datenstruktur an, die "Suffix Array" heißt. Man könnte sich nämlich überlegen, an welcher Stelle sich eine Optimierung vornehmen ließe:

Eingentlich braucht man überhaupt nicht alle Teilstrings miteinander zu vergleichen, sondern nur diese, die sich ähnlich sind. Dafür verwendet man einen Array von Zeigern. Jeder Zeiger zeigt auf eine Teil des Teilstrings. Ein Beispiel:

a[0]: ANANAS
a[1]: NANAS
a[2]: ANAS
a[3]: NAS
a[4]: AS
a[5]: S

Das erreicht man folgendermaßen:

#define MAXN 5000000
char c[MAXN], *a[MAXN];
while (ch = getchar()) != EOF
a[n] = &c[n]
c[n++] = ch
c[n] = 0

Wenn ein Teil des Wortes jetzt in zwei verschiedenen Suffixen auftaucht, dann muß es auch zweimal im gesamten Wort auftauchen. Dafür sortiert man jetzt den Array mit Quicksort.

a[0]: ANANAS
a[1]: ANAS
a[2]: AS
a[3]: NANAS
a[4]: NAS
a[5]: S

Nun erhält man durch einfaches vergleichen der benachbarten Wörter den längsten Teilstring des Wortes (hier: ANA).

for (i = 0; i++; i < n)
if comlen(a[i], a[i+1]) > maxlen
maxlen = comlen(a[i], a[i+1])
maxi = i
printf("%.*s\n, maxlen, a[maxi])

Bei einer typischen Eingaben liegt die Laufzeit bei O(n log n).