Informelle Problemstellung:
Bei einer gegebenen Zeichenfolge, z. B. , möchten wir einige Buchstaben rot und einige Buchstaben blau (und einige überhaupt nicht) färben, sodass das Lesen nur der roten Buchstaben von links nach rechts dasselbe Ergebnis ergibt wie das Lesen nur der blauen Buchstaben.
Im Beispiel könnten wir sie folgendermaßen einfärben:
Wir sagen daher, dass eine wiederholte Folge von ACCABBAB ist . Es ist auch eine am längsten wiederholte Folge (die leicht zu überprüfen ist).A C C A B B A B
Können wir die längsten wiederholten Teilfolgen effizient berechnen?
Formale Frage:
Ist es NP-schwer, sich für eine Zeichenkette und ein k zu entscheiden , ob eine wiederholte Folge der Länge in der Zeichenkette existiert?
- Wenn ja: Welches Problem kann auf dieses Problem reduziert werden?
- Wenn nicht: Was ist ein effizienter Algorithmus? (Natürlich kann dieser Algorithmus dann verwendet werden, um eine längste wiederholte Teilsequenz zu berechnen.)
Bonus-Frage:
Wird es immer eine wiederholte Folge der Länge wenn die Größe des Alphabets durch eine Konstante begrenzt ist?
(Dies gilt bekanntermaßen für binäre Alphabete.)
Bearbeiten 2: Die negative Antwort auf die Bonusfrage ist bereits für Alphabete mit einer Größe von mindestens . Tatsächlich gibt es für Alphabete der Größe Σ Zeichenfolgen mit den längsten wiederholten Teilfolgen mit einer Länge von lediglich O (n · Σ ^ {- 1/2}) . Zufällige Zeichenfolgen genügen, um dies zu zeigen. Das Ergebnis gab es bereits, aber ich habe es übersehen.Σ O ( n · Σ - 1 / 2 )
Bearbeiten: Hinweis:
Einige Leute meinen "Teilzeichenfolge", wenn sie "Teilfolge" sagen. Ich nicht. Dies ist nicht das Problem, zweimal einen Teilstring zu finden.
Antworten:
Dies kann in gelöst werdenG ( i , j ) S S[ i ] = S[ j ] u v u v
Polynomzeitdurch Konstruieren eines Graphen wobei jeder Knoten einen Punkt in einer wiederholten Folge von so dass . Kante zwischen Knoten und bedeutet, dass mit fortgesetzt werden kann , um eine wiederholte Folge der Länge 2 zu bilden.( i , j ) S S [ i ] = S [ j ] u v u v1. Finden Sie die Knoten. Dies kann in indem für jedes Zeichen eine sortierte Liste von Indizes erstellt und anschließend die eindeutigen Paare aufgelistet werden. Es gibt nicht mehr als Knoten.c m = n 2O ( n2) c m = n2
2. Finden Sie die Kanten. Es braucht Zeit, um zu prüfen, ob der Knoten durch den Knoten fortgesetzt werden kann. Wenn alle Paare berücksichtigt werden, dauert dieser Schritt Zeit.u v ( u , v ) O ( m 2 )O ( 1 ) u v ( u , v ) O ( m2)
3. Beachten Sie, dass der längste Pfad in möglicherweise keine gültige wiederholte Teilsequenz ist. Betrachten Sie die Pfade und . Wenn es eine Kante ist eine gültige wiederholte Teilfolge der Länge 3. Daher dauert es , alle wiederholten Teilfolgen der Länge 3 zu finden. Im allgemeinen Fall dauert es linear, um zu überprüfen, ob zwei gültige Pfade vorhanden sind der Länge kann zu einem gültigen Pfad der Länge kombiniert werden .a b b c a c a b c O ( m 4 ) n n + 1G a b b c a c a b c O ( m4) n n + 1
4. Wiederholen Sie Schritt 3, bis keine Pfade mehr gefunden werden.
quelle