Wir haben einen String.
ABAEABABEABE
Nun müssen wir prüfen, ob es eine Teilzeichenkette gibt, der als nächste eine Teilzeichenkette folgt, die genau der ersten entspricht.
In diesem Beispiel:
ABAEAB ABE ABE
ABE folgt ABE und das sind zwei identische Teilstrings.
In diesem Beispiel:
AAB
Es wäre einfach A, weil A von einem anderen A gefolgt wird.
In diesem Beispiel:
ABCDEFGHIJKLMNO
Es gibt keinen solchen Teilstring, daher wäre die Antwort NEIN.
Ich habe nur einen Algorithmus gefunden, der in O (n ^ 2) laufen würde. Das bekommt Hashes und seine Präfixe. Dann erweitern wir für jeden Buchstaben einfach und überprüfen alle Wörter, die auf diesem Buchstaben enden. Es gibt n Buchstaben. Wir müssen es n-mal erweitern. Also ist es O (n ^ 2). Ich glaube, dass es einen O (n log n) -Algorithmus für dieses Problem geben sollte.
Hat jemand eine bessere Idee?
Ich denke, Sie wollen die längste Teilkette, die diesem Muster folgt.
Als Erstes erstellen Sie einen Suffixbaum der Eingabezeichenfolge. Mit Ukkonens Algorithmus ist dies O (n) .
Wie übersetzt sich nun die von Ihnen angegebene Bedingung in den Suffixbaum? Zunächst einmal suchen Sie nach einem wiederholten Teilstring [1] . Wiederholte Teilstrings erscheinen als interne Knoten des Suffixbaums. Die maximale Anzahl an Knoten in einem Suffix Baum, der aus einer Zeichenfolge n -char erstellt wurde, ist 2n - 1 .
Sie können einen Max-Heap erstellen, der solche wiederholten Teilstrings enthält, indem Sie deren Länge (Anzahl der Zeichen) verwenden. Sie machen NOT Teilstrings der Länge besser als N / 2 (siehe [1]) . Dies ist O (N) wobei N die Anzahl der internen Knoten des Suffixbaums ist. Für jeden Suffixbaum:
0 ≤ N ≤ n - 2
Nun nehmen Sie das Maximum aus der Prioritätswarteschlange und bearbeiten den internen Knoten i , den Sie erhalten haben:
Sei n die Länge der Abfragezeichenfolge.
Daher ist die Gesamtkomplexität im ungünstigsten Fall die Summe der obigen und ist O (n².log (n)) .
Ich habe den obigen Algorithmus gemacht ... Daher ist es suboptimal, wenn Sie mutig genug sind, können Sie durchgehen Dieses Papier beschreibt einen linearen Zeitalgorithmus! In jedem Fall sind Suffix-Bäume ein Schlüssel zu diesem Problem, daher schlage ich vor, dass Sie sie gründlich studieren.
[1] : Warnung, wiederholte Teilstrings können sich teilweise überlappen!
[2] Eigentlich ist die Worst-Case-Komplexität besser als diese naive Obergrenze, aber ich weiß nicht, wie ich das beweisen soll (noch ?!). Wenn zum Beispiel n - 2 interne Knoten vorhanden wären, würde dies bedeuten, dass die ursprüngliche Zeichenfolge aus n Vorkommen desselben Zeichens besteht. In diesem Fall ist die erste Teilzeichenfolge, die wir prüfen, eine Übereinstimmung = & gt; es ist O (n.log (n)).
[3] : Wenn wir die Heap-Konstruktion durch eine reguläre Sortierung ersetzen ( O (n.log (n)) ), wird der letzte Vergleichsschritt in
Dieses Problem könnte mit dem Main-Lorentz-Algorithmus "Divide and Conquer" gelöst werden:
Michael Main, Richard J. Lorentz. Ein O (n log n) -Algorithmus zum Auffinden aller Wiederholungen in einem String [1982]
Bearbeiten : Algorithmusbeschreibung und C ++ - Implementierung in Russisch (möglicherweise mit Chrome-Browser übersetzt) )
Es gibt auch linear-time algorithm (weiß nicht über praktisch Implementierungen)