Algorithmus, um die Länge der längsten Suffix zwischen einem String und einem Präfix des String zu finden

Question

Input:

Es gibt eine lange String S und wir haben eine Reihe von ganzen Zahlen A welche die Präfixe des String bezeichnet S wie A[i] bezeichnet die Vorsilbe S[0..A[i]]

Output:

ein Array Output[] von der gleichen Größe wie A wo Output[i] die Länge des längsten passenden Suffix S[0..A[i]] und S ist

Probe Input:

S = "ababa" 
A[]=[0, 1, 2, 3, 4] 

Beispielausgabe:

Output[]=[1,0,3,0,5]

Der naive Algorithmus, Ich habe für jeden A[i] passen Sie einfach die Anzahl der Zeichen zwischen S[0..A[i]] und S vom Ende der beiden Strings. Aber dieser Algorithmus ist O(n^2) wobei n die Länge des ursprünglichen String ist S.

Frage:
Gibt es einen besseren Algorithmus, der vor Prozesse der String S und dann schnell die längste Länge Suffix für die gesamte zurückkehren Eingabe-Array?

Answer 1

Dies ist nur ein Z-function der umgekehrten String. Der kleine Unterschied ist, dass das erste Element der Z-Funktion so gewählt wird, dass es gleich der Länge S ist.Es gibt einen Algorithmus, um die Z-Funktion von einer Zeichenkette in O (n)

und der Algorithmus für dieses Problem zu berechnen, ist wie folgt:

• S‘: = RÜCKWÄRTS S
• Z : = Z-Funktion S‘
• für jeden i, Output [i]: = Z [Len (S) - A [i] - 1]

zum Beispiel:

S = "baabaaa" 
A[] = [0,1,2,3,4,5,6] 
Output[] should be [0,1,2,0,1,2,7] 

S' = "aaabaab" 
Z = Z-function(S') = [7,2,1,0,2,1,0] (with the first element chosen to be Len(S)) 

Answer 2

Der Algorithmus/Datenstruktur Sie suchen, genannt Suffixbaum es eine Worst-Case Komplexität O(n log n)

In der Informatik ist ein Suffix-Baum (auch PAT Baum oder in einem genannt früher form, position tree) ist ein komprimierter Trie, der alle Suffixe des gegebenen Textes als ihre Schlüssel und Positionen im Text als deren Werte enthält. Suffix-Bäume ermöglichen besonders schnelle Implementierungen von vielen wichtigen String-Operationen von . (wiki)

Here können Sie einige Folien finden, die die Funktionalität und Implemenation im Detail zu erklären