Ist einer von ihnen bei n Zeichenfolgen ein Teilstring eines anderen?

Angenommen, wir erhalten eine Sammlung von Zeichenfolgen, . Ich würde gerne wissen, ob eine dieser Zeichenfolgen eine Teilzeichenfolge einer anderen Zeichenfolge in der Sammlung ist. Mit anderen Worten, ich möchte einen Algorithmus für die folgende Aufgabe: $n$ $S_1,\dots,S_n$

Eingabe: $S_1,\dots,S_n$

Ausgabe: so dass eine von und , oder Keine, wenn kein solches existiert $i,j$ $S_i$ $S_j$ $i\ne j$ $i,j$

Gibt es dafür einen effizienten Algorithmus?

Wenn wir "Teilzeichenfolge" durch "Präfix" ersetzen, gibt es einen effizienten Algorithmus (sortieren Sie die Zeichenfolgen und führen Sie dann einen linearen Scan durch, um benachbarte Zeichenfolgen zu vergleichen; durch Sortieren wird sichergestellt, dass Teilzeichenfolgen benachbart sind). Es scheint jedoch schwieriger zu testen, ob eine Zeichenfolge eine Teilzeichenfolge einer anderen Zeichenfolge ist. Ein naiver Algorithmus besteht darin, über alle Paare zu iterieren , dies erfordert jedoch -Substring-Tests. Gibt es einen effizienteren Algorithmus? $i,j$ $\Theta(n^2)$

Ich denke, wir könnten dies "All-Pair-Teilstringtest" oder so etwas nennen.

Mein letztendliches Ziel ist es, die Sammlung so zu beschneiden, dass kein String ein Teilstring eines anderen ist, indem jeder entfernt wird, der ein Teilstring von etwas anderem in der Sammlung ist.

Hinweis: Suffix-Array.

Pseudonym

Als Randnotiz ist nicht korrekt, wenn Sie Teilzeichenfolgen entfernen, sobald Sie sie finden. Es wird weniger sein. Außerdem sollten Sie nach Länge sortieren, da eine längere Zeichenfolge nicht in einer kürzeren Zeichenfolge angezeigt werden kann. Wieder ist hier falsch.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta(n^2)$

Alexis Wilke

@AlexisWilke, ist richtig: Das ist die Anzahl der Teilstringtests im schlimmsten Fall (im schlimmsten Fall ist kein String ein Teilstring eines anderen). Wenn Sie nach Länge sortieren, erhalten Sie nur den Faktor zwei, was die Asymptotik nicht beeinflusst.

Θ (n^{2})

$\Theta(n^2)$

Antworten:

Sie können einen Suffixbaum in linearer Zeit erstellen und prüfen, ob ein innerer Knoten vorhanden ist, der einer vollständigen Zeichenfolge entspricht (konstante Zeit pro Knoten).

Nehmen wir genauer an, wir erhalten die Zeichenfolgen . $s_1, \dots, s_n \in \Sigma^*$

Erstellen Sie einen (verallgemeinerten) Suffixbaum aus mit paarweise unterschiedlichen Terminalmarkierungen . $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ $n$ $\$_1,\dots,\$_n \notin \Sigma$

Mit dem Ukkonen-Algorithmus kann dies in linearer Zeit erfolgen. linear in der Summe aller Saitenlängen.
$(i,j)$ $s_i[j..|s_i|]$ $s_i$ $n$ $(i,0)$

Dies erfordert eine lineare Zeit in der Baumgröße, die selbst in der Eingabegröße linear ist.
$(i,0)$ $\$_i$ $(i,0)$

Dies dauert wieder lineare Zeit.

Die unterschiedlichen Endmarkierungen sind nicht wirklich notwendig; Eine einzige, die zum Beenden aller Zeichenfolgen verwendet wird, ist völlig ausreichend, solange Sie mehrere Beschriftungen pro Blatt zulassen.

Raphael
quelle