Angenommen, ich möchte die längste Untersequenz finden, so dass die erste Hälfte der Untersequenz dieselbe wie die zweite Hälfte davon ist.Finden der längsten ähnlichen Untersequenz in einer Zeichenkette
Zum Beispiel: In einem String abkcjadfbck ist das Ergebnis abcabc, da abc in der ersten und zweiten Hälfte wiederholt wird. In einem Schritt aaa ist das Ergebnis aa.
Diese Aufgabe kann als eine Kombination aus zwei bekannten Problemen behandelt werden.
Also, was ich von der Methode verstehe ist, dass .. von i = 1: n, erstellen Sie zwei Zeichenfolgen und nur längste gemeinsame Teilsequenz über sie durchführen. Es wird also die Reihenfolge von n * (n * n) sein, um die längste Teilfolge mit ähnlichen Hälften zu finden. Aber können wir alle möglichen Strings erzeugen (nicht nur die längsten)? Zum Beispiel, für aaa, werden wir 3 solcher Strings möglich aa, aa, aa haben. (erstes "a" mit zweitem "a", erstes "a" mit drittem "a", zweites "a" mit drittem "a") – test
Die längste Teilfolge mit diesen Algorithmen zu durchsuchen, ist O (N^2 log N), weil mit Bei der Suche nach dem Goldenen Schnitt müssen Sie die Zeichenfolge nicht an jeder möglichen Position aufteilen. Aber das erlaubt nicht, alle Subsequenzen zu bekommen. Das Generieren aller Subsequenzen ist eine völlig andere Aufgabe und sollte mit anderen Methoden behandelt werden. –
In einem ersten Durchlauf über inputString können wir zählen, wie oft jedes Zeichen auftritt, und diejenigen mit dem ersten entfernen.
input: inputString
data strucutres:
Set<Triple<char[], Integer, Integer>> potentialSecondWords;
Map<Char, List<Integer>> lettersList;
for the characters c with increasing index h in inputString do
if (!lettersList.get(c).isEmpty()) {
for ((secondWord, currentIndex, maxIndex) in potentialSecondWords) {
if (there exists a j in lettersList.get(c) between currentIndex and maxIndex) {
update (secondWord, currentIndex, maxIndex) by adding c to secondWord and replacing currentIndex with j;
}
}
if potentialSecondWords contains a triple whose char[] is equal to c, remove it;
put new Triple with value (c,lettersList.get(c).get(0), h-1) into potentialSecondWords;
}
lettersList.get(c).add(h);
}
find the largest secondWord in potentialSecondWords and output secondWord twice;
Also dieser Algorithmus geht einmal über das Array, für jeden Index zu schaffen, wo es Sinn macht, ein Dreibettzimmer das Potential zweite Wort im aktuellen Index beginnend darstellt und aktualisiert alle möglichen zweiten Worte.
Mit einer geeigneten Listenimplementierung und n, die die Größe von inputString ist, hat dieser Algorithmus Worst-Case-Laufzeit O (n²), z. für ein^n.
Können Sie bitte den Algo erklären? – test
Ich verstehe es nicht. Wo ist 'abc' irgendwo in der ersten Saite? Und warum ist das Ergebnis der zweiten Saite nicht "aaa"? Das ist natürlich länger. –
Ich denke Subsequenz bedeutet nicht, dass die Indizes aufeinander folgen müssen. Die resultierende aa ist entweder [Index 0, Index 1], [Index 1, Index 2] oder [Index 0, Index 2]. – DaveFar
aaa hat ein "aa" Ergebnis, weil in "aa" die erste Hälfte gleich ist wie die zweite Hälfte. – test