Berechnung der längsten gemeinsamen Teilzeichenfolge von zwei Zeichenfolgen mit Suffix-Arrays

Nachdem ich gelernt habe, wie man ein Suffix-Array in -Komplexität erstellt, möchte ich die Anwendungen der Suffix-Arrays kennenlernen. Eine davon besteht darin, die längste gemeinsame Teilzeichenfolge zwischen zwei Zeichenfolgen in -Zeit zu finden. Ich habe im Internet folgenden Algorithmus gefunden:O ( N $O(N)$$O(N)$

1. Füge die beiden Saiten und zu einer SaiteB A $A$$B$$AB$
2. Berechnen Sie das Suffix-Array von$AB$
3. Berechnen Sie das Array (Longest Common Prefix)$LCP$
4. Die Antwort ist der größte Wert$LCP[i]$

Ich habe versucht, es zu implementieren, aber da viele Implementierungsdetails nicht angegeben wurden (dh, wenn die Zeichenfolgen verkettet werden, sollte ich ein Sonderzeichen dazwischen setzen ( )?), mein Code in vielen Testfällen fehl. Könnte jemand mehr über diesen Algorithmus arbeiten?$AcB$

Danke im Voraus.

Hinweis: Ich kann die Richtigkeit dieses Algorithmus nicht garantieren. Ich habe es in einem Blog gefunden und bin mir nicht sicher, ob es funktioniert. Wenn Sie denken, dass es falsch ist, schlagen Sie bitte einen anderen Algorithmus vor.

Ihr Algorithmus ist falsch . Ich gehe davon aus, dass Sie wissen, wie man das Suffix-Array und das LCP-Array eines Strings berechnet, das heißt, ihre effiziente Implementierung. Wie in den Kommentaren erwähnt, sollten Sie versuchen zu verstehen, was jede Komponente ist und warum sie funktioniert.

Zuallererst ist das Suffix-Array ( ) einer Zeichenfolge. Ein Suffix-Array besteht im Wesentlichen aus allen Suffixen der Zeichenfolge die in aufsteigender lexikografischer Reihenfolge angeordnet sind. Genauer gesagt, der Wert zeigt an, dass das Suffix von ausgehend von Position rangiert in der lexikographischen Ordnung aller Suffixe von .S S A [ i ] S S A [ i ] i $SA$$S$$SA[i]$$S$$SA[i]$$i$$S$

Als nächstes kommt das Array. gibt die Länge des längsten gemeinsamen Präfixes zwischen den Suffixen ab und . Das heißt, es verfolgt die Länge des längsten gemeinsamen Präfixes unter zwei aufeinanderfolgenden Suffixen von wenn es in lexikografischer Reihenfolge angeordnet ist.L C P [ i ] S A [ i - 1 ] S A [ i ] $LCP$$LCP[i]$$SA[i-1]$$SA[i]$$S$

Betrachten Sie als Beispiel die Zeichenfolge . Die lexikografisch geordneten Suffixe lauten , also ist für ein 1-indiziertes Array. Das Array wäre .{ a , a b b ein b c a , a b c a , b ein b c a , b b ein b c a , b c a , c a } S A = [ 7 , 1 , 4 , 3 , 2 , 5 $S = abbabca$$\{a, abbabca, abca, babca, bbabca, bca, ca\}$L C P L C P = [ - , 1 , 2 , 0 , 1 , 1 , 0 $SA = [7, 1, 4, 3, 2, 5, 6]$$LCP$$LCP = [-, 1, 2, 0, 1, 1, 0]$

Wenn wir nun zwei Zeichenfolgen und , verketten wir sie als , wobei ein Zeichen ist, das sowohl in als auch in nicht vorhanden ist . Der Grund für die Auswahl eines solchen Zeichens ist, dass bei der Berechnung des LCP aus zwei Suffixen, z. B. und , der Vergleich am Ende der ersten Zeichenfolge abgebrochen wird (da es nur einmal vorkommt, werden zwei verschiedene Suffixe niemals auftreten) haben Sie es in der gleichen Position), und wird nicht in die andere Zeichenfolge "überlaufen" .B S = A # B # A B a b # d a b d a b $A$$B$$S = A\#B$$\#$$A$$B$$ab\#dabd$$abd$

Nun ist zu sehen, dass Sie in der Lage sein sollten zu erkennen, warum Sie nur aufeinanderfolgende Werte im Array (das Argument basiert auf Widersprüchen und der Tatsache, dass die Suffixe in in lexikographischer Reihenfolge vorliegen). Überprüfen Sie das Array weiterhin auf den Maximalwert, sodass die beiden verglichenen Suffixe nicht zu derselben ursprünglichen Zeichenfolge gehören. Wenn sie nicht zu derselben ursprünglichen Zeichenfolge gehören (eine beginnt in und die andere in ), ist der größte derartige Wert die Länge der größten gemeinsamen Teilzeichenfolge.S A L C P A $LCP$$SA$$LCP$$A$$B$

Als Beispiel betrachten und . Dann ist . Sortierte Suffixe sind . $A = abcabc$$B = bc$$S = abcabc\#bc$$\{abc\#bc, abcabc\#bc, bc, bc\#bc, bcabc\#bc, c, c\#bc, cabc\#bc\}$
$\begin{align*} SA &= [4, 1, 8, 5, 2, 9, 6, 3, 7] \\ LCP &= [-, 3, 0, 2, 2, 0, 1, 1, 0] \end{align*}$

Der größte Wert ist , aber er gilt für und , die beide in der Zeichenfolge . Also ignorieren wir das. Andererseits ist für (entspricht dem Suffix von ) und (entspricht dem Suffix von ). Dies ist also die längste gemeinsame Teilzeichenfolge zwischen den beiden Zeichenfolgen. Für die eigentliche Teilzeichenfolge bekommen Sie eine Länge nehmen (Wert des größten machbar ) String ausgehend von entweder oderS A [ 1 ] S A [ 2 ] Ein L C P [ 4 ] = 2 S A [ 3 ] b c B S A [ 4 ] b c ein b c # b c A 2 L C P S A [ 3 ] S A $LCP[2] = 3$$SA[1]$$SA[2]$$A$$LCP[4] = 2$$SA[3]$$bc$$B$$SA[4]$$bcabc\#bc$$A$$2$ $LCP$$SA[3]$b $SA[4]$ , die .$bc$

Der Algorithmus, den Sie online gefunden haben, ist nicht ganz korrekt. Wie von Paresh erwähnt, wird es in dem von ihm gegebenen Beispiel scheitern.

Wenn Sie jedoch sicherstellen, dass beim Überprüfen des LCP nur das LCP von Teilzeichenfolgen verschiedener Zeichenfolgen überprüft wird. Wenn Sie beispielsweise die LCS der Zeichenfolgen A und B finden, müssen Sie sicherstellen, dass die benachbarten Einträge des Suffix-Arrays bei der Überprüfung auf LCP nicht beide von derselben Zeichenfolge stammen.

Weitere Details hier .

Ich denke , so etwas wie der Algorithmus Sie zitieren sollte in der Tat funktionieren , wenn ein Zeichen , das nicht Teil des Zeichensatzes ist als Trennzeichen verwendet wird, und das Suffix / Präfix - Arrays werden errichtet , um auszuschließen , alle Strings, die den Separator enthalten, wahrscheinlich die Absicht , die Designer. Dies entspricht im Wesentlichen der Erstellung von Suffix / Präfix-Arrays für die beiden separaten Zeichenfolgen.

Es wäre hilfreich für zukünftige Verweise, wenn Sie einen Link zum Algorithmus veröffentlichen würden. Beachten Sie, dass Wikipedia den Algorithmus dafür in Pseudocode und vielen anderen Algorithmen hat. und es gibt Implementierungen in den meisten Standardsprachen, die online verfügbar sind.