Ich muss die längste sich wiederholende Zeichenfolge in der Teilzeichenfolge finden. Angenommen, ich habe die Zeichenfolge "bannana"
Wikipedia sagt folgendes:
In der Informatik ist das längste wiederholte Teilstring-Problem das Problem, die längste Teilzeichenfolge einer Zeichenfolge zu finden, die bei mindestens zweimal. In der Abbildung mit der Zeichenkette "ATCGATCGA $" die längste Wiederholte Teilzeichenfolge ist "ATCGA"
Also nehme ich an, dass es für den String "bannana" zwei gleich lange Teilstrings gibt (wenn nicht, bitte, bitte): "an" und "na" .
Wikipedia sagt , dass zu diesem Zweck Suffix-Bäume verwendet werden. Um genauer zu sein, hier ist Zitat, wie man es macht (das scheint mir eher unterscheidbar als Definition auf wikipedia ):
Erstellen Sie einen Suffixbaum, und suchen Sie dann den höchsten Knoten mit mindestens 2 Nachkommen.
Ich habe mehrere Implementierungen von Suffixbäumen gefunden. Der folgende Code stammt von hier :
%Vor% für die Zeichenfolge "bannana" gibt die folgende Struktur zurück:
Eine weitere Implementierung ist online von hier , für den String "bannana" gibt es folgenden Baum zurück:
Fragen:
"an" und "na" strings? 1. Wie kann ich aus diesen Graphen "an" und "na" Strings bekommen?
Erstellen Sie einen Suffixbaum, und suchen Sie den höchsten Knoten mit mindestens zwei Nachkommen.
string-node verkettet Zeichenketten für jeden Knoten von der Wurzel bis zu diesem Knoten. highest node ist ein Knoten mit der maximalen Länge string-node .
Siehe Baum in meiner Antwort für die zweite Frage. (3:n) haben 2 Nachkommen und Pfad zum Knoten ist (2:a)->(3:n) , verkettet ist an . Und auch für (5:a) get na .
2. Wie Sie sehen können, sind Bäume verschieden, sind sie gleichwertig oder nicht, wenn ja, warum sind sie anders, wenn nicht welcher Algorithmus richtig ist?
Diese Bäume sind anders. Erstellen Sie den zweiten Baum für die Zeichenfolge "bannana$" (
wie im ersten Baum):
3. Wenn Perl-Implementierung falsch ist, gibt es irgendeine funktionierende Implementierung für Perl / Python?
Ich kenne Perl nicht, aber der Baum ist korrekt gebaut.
4. Ich habe über den Algorithmus von Ukkonen gelesen, der auch auf der Seite mit dem zweiten Beispiel erwähnt wird (ich habe nicht herausgefunden, ob die Online-Version diesen Algorithmus verwendet oder nicht), benutzt eines der erwähnten Beispiele diesen Algorithmus? Wenn nicht, ist Algorithmus langsamer oder hat irgendwelche Nachteile im Vergleich zu Ukkonen?
Ich sagte früher, dass ich Perl nicht kenne, aber es ist eine Zeile in erster algorthim bedeutet, dass es mindestens funktioniert O(n^2) ( n es ist Länge Zeichenfolge):
Der Ukkonen-Algorithmus arbeitet linear mit O(n) .
Erster rekursiver Algorithmus, der sich auf den belegten Speicher auswirken kann.
Tags und Links algorithm string perl tree suffix-tree