Berechnen der längsten gemeinsamen Substring von zwei Zeichenfolgen mit Suffix -Arrays

Question

Nachdem ich gelernt habe, wie man ein Suffix -Array in $ O (n) $ -Komplexität baut, bin ich daran interessiert, die Anwendungen der Suffix -Arrays zu entdecken. Eine davon ist das längste gemeinsame Substring zwischen zwei Strings in $ o (n) $ time. Ich fand im Internet den folgenden Algorithmus:

1. Zusammenführen die beiden Zeichenfolgen $ a $ und $ B $ in eine Zeichenfolge $ AB $
2. Berechnen Sie das Suffix -Array von $ ab $
3. Berechnen Sie das Array $ LCP $ (längst gemeinsam)
4. Die Antwort ist der größte Wert $ lcp [i] $

Ich habe versucht, es umzusetzen, aber so wie viele Implementierungsdetails nicht gesagt wurden (dh bei der Verkettung der Saiten, sollte ich einen speziellen Charakter zwischen ihnen ($ ACB $) setzen, mein Code ist in vielen Testfällen fehlgeschlagen. Könnte jemand mehr auf diesen Algorithmus ausarbeiten?

Danke im Voraus.

Notiz: Ich garantiere nicht die Richtigkeit dieses Algorithmus. Ich habe es in einem Blog gefunden und bin mir nicht sicher, ob es funktioniert. Wenn Sie der Meinung sind, dass es falsch ist, schlagen Sie bitte einen anderen Algorithmus vor.

Answer 1

Ihr Algorithmus ist falsch. Ich gehe davon aus, dass Sie wissen, wie man das Suffix -Array und das LCP -Array einer Zeichenfolge berechnet, dh ihre effiziente Implementierung. Wie in den Kommentaren hervorgeht, sollten Sie versuchen zu verstehen, was jede Komponente ist und warum sie funktioniert.

Zunächst einmal ist das Suffix -Array ($ sa $) einer Zeichenfolge. Ein Suffix -Array ist im Grunde alle Suffixe der String $ S $, die in aufsteigender lexikografischer Reihenfolge angeordnet sind. Insbesondere zeigt der Wert $ sa [i] $, dass das Suffix von $ s $ von Position $ sa [i] $ $ i $ in der lexikografischen Bestellung aller Suffixe von $ s $ eingestuft wird.

Als nächstes kommt das $ lcp $ arrray. $ Lcp [i] $ zeigt die Länge der längsten gemeinsamen Präfix zwischen den Suffixe Ab $ sa [i-1] $ und $ sa [i] $. Das heißt, es verfolgt die Länge des längsten gemeinsamen Präfixes unter zwei aufeinanderfolgenden Suffixen von $ s $, wenn sie in lexikografischer Reihenfolge angeordnet sind.

Betrachten Sie beispielsweise die Zeichenfolge $ S = Abbabca $. Die Suffixe in lexikografischer Reihenfolge wären $ {A, Abbabca, ABCA, Babca, Bbabca, BCA, Ca } $, also $ sa = [7, 1, 4, 3, 2, 5, 6] $ für a 1 -Idexed Array. Das $ lcp $ array wäre $ lcp = [-, 1, 2, 0, 1, 1, 0] $.

Angesichts von zwei Saiten $ a $ und $ B $ verkettet wir sie als $ s = a #b $, wobei $ #$ ein Charakter ist, der nicht sowohl in $ a $ als auch $ B $ vorhanden ist. Der Grund für die Auswahl eines solchen Charakters ist, dass bei der Berechnung des LCP von zwei Suffixen $ ab #dabd $ und $ abd $, der Vergleich am Ende der ersten Zeichenfolge abbrechen wird (da er nur einmal auftritt, zwei, zwei Unterschiedliche Suffixe werden es niemals in derselben Position haben) und nicht "Überlauf" in die andere Zeichenfolge.

Nun ist ersichtlich, dass Sie in der Lage sein sollten zu sehen, warum Sie nur aufeinanderfolgende Werte im $ LCP $ -Rarray sehen müssen (das Argument basiert auf dem Widerspruch und der Tatsache, dass die Suffixe in $ sa $ in lexikografischer Reihenfolge sind). Überprüfen Sie den $ LCP $ Array auf den Maximalwert weiter so dass Die beiden verglichenen Suffixe gehören nicht zur gleichen ursprünglichen Zeichenfolge. Wenn sie nicht zur gleichen Original -Zeichenfolge gehören (einer beginnt in $ a $ und die andere in $ B $), dann ist der größte derartige Wert die Länge des größten gemeinsamen Substrings.

Betrachten Sie beispielsweise $ A = ABCABC $ und $ B = BC $. Dann $ s = abcabc #bc $. Sortierte Suffixe sind $ {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 jetzt $ lcp [2] = 3 $, aber es ist für $ sa [1] $ und $ sa [2] $, beide beginnen in der Zeichenfolge $ a $. Also ignorieren wir das. Auf der anderen Seite ist $ lcp [4] = 2 $ für $ sa [3] $ (entspricht dem Suffix $ bc $ von $ b $) und $ sa [4] $ (entsprechend Suffix $ bcabc #bc $ von $ a $). Dies ist also das längste häufige Substring zwischen den beiden Saiten. Um das tatsächliche Substring zu erhalten, nehmen Sie eine Länge $ 2 $ (Wert der größten machbar $ Lcp $) substring ab $ sa [3] $ oder $ sa [4] $, was $ bc $ ist.

Answer 2

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

Wenn Sie jedoch sicherstellen, dass Sie beim Überprüfen der LCP nur die LCP von Untergräben verschiedener Zeichenfolgen überprüfen. Wenn Sie beispielsweise die LCs der Saiten A und B finden, müssen Sie sicherstellen, dass die angrenzenden Einträge des Suffix -Arrays während der Überprüfung auf LCP nicht von derselben Zeichenfolge sind.

Mehr Details hier.

Answer 3

Ich denke, so etwas wie der Algorithmus, den Sie zitieren ausschließen Alle Saiten, die den Trennzeichen enthalten, wahrscheinlich die Absicht des Designers. Dies entspricht im Grunde genommen dem Gebäude -Suffix-/Präfix -Arrays für die beiden separaten Zeichenfolgen.

Es wäre hilfreich für Future Ref, wenn Sie einen Link zum Algorithmus veröffentlicht haben. beachten Sie, dass Wikipedia hat den Algorithmus dafür in Pseudocode und vielen anderen Algorithmen. und es gibt Implementierungen in den meisten Standardsprachen online.