Folge einer Zeichenfolge, aber nicht von anderen

7

Lassen Σ sei ein Alphabet und lass x+,x1,,xnΣZeichenfolgen über diesem Alphabet sein. Rufen Sie eine Zeichenfolge aufsΣ gut wenns ist eine Folge von x+ aber keine Folge von x1,,xn.

Gegeben x+,x1,,xnIch suche die kürzeste gute Saite s. Gibt es dafür einen vernünftigen Algorithmus? Ich interessiere mich für einen praktischen Algorithmus, auch wenn seine Laufzeit im ungünstigsten Fall nicht großartig ist. In meiner Domäne die Zeichenfolgenx+,x1,,xn mag ziemlich lang sein, aber ich gehe davon aus, dass es eine gute Saite geben wird s das ist ziemlich kurz, falls das hilft.

Der Fall n=1wird von der kürzesten Teilsequenz einer Zeichenfolge behandelt, das ist keine Teilsequenz einer anderen Zeichenfolge , aber ich muss mich mit dem Fall befassenn>1.

DW
quelle
1
Mein Standardvorschlag: Suffixbaum? Die Zeichenfolge, nach der Sie suchen, ist der Knoten mit der kleinsten Ebene unter allen, die nur eine haben(x+,_)als Blatt. Oh, warten Sie ... sub - Sequenz ? Verdammt. Hm.
Raphael
Ist das Problem ohne x+die doppelte bis längste gemeinsame Teilfolge? Wenn ja, kann vielleicht etwas in diese Richtung getan werden. (Das Aufzählen allgemeiner Nicht-Teilsequenzen durch Erhöhen der Länge würde Ihr Problem lösen.)
Raphael
Ich glaube, dass Aryabhatas DP ziemlich einfach auf die erweitert werden kann n>1 Fall: einfach verwenden n Tabellen, eine für jede xiund dann nach dem Kleinsten suchen Lso dass für jeden Tischiund für einige k, is_there[i,k,t,L]=false. Das wird dir die Länge sagen (L) und das letzte Zeichen (x+[k]), aber ich bin noch nicht sicher, wie ich die früheren Zeichen extrahieren soll ...
j_random_hacker
2
@j_random_hacker, ich denke nicht, dass das funktioniert. Das könnte eine Teilfolge von auswählenx+ von Länge L das ist keine Folge von x1und eine andere Folge von x+ von Länge L das ist keine Folge von x2. (Der erste könnte eine Teilfolge von seinx2und der zweite eine Teilfolge von x1, was schlecht wäre.) Wir brauchen eine einzige Teilsequenz von x+, nicht für jeden einen eigenen xi. Oder habe ich etwas Kluges an Ihrer Idee vermisst?
DW
3
Wenn Sie nicht unbedingt die kürzeste Teilsequenz benötigen, können Sie die Tatsache verwenden, dass, wenn eine Zeichenfolge s ist keine Folge von irgendwelchen xidann ist es auch keine Folge einer Verschachtelung der Saitenxi. Sie können also viele verschiedene Möglichkeiten ausprobieren, um das zufällig zu verschachtelnn Saiten xi in eine einzelne Zeichenfolge und für jede solche Verschachtelung yjSuchen Sie nach einer Teilsequenz zj von x+ das vermeidet, eine Folge von zu sein yj mit Aryabhatas DP, und wählen Sie, was auch immer zjist am kürzesten.
j_random_hacker

Antworten:

1

Fehler

Zunächst habe ich in den Kommentaren einige Fehler gemacht: Sowohl die ursprüngliche Behauptung, die ich über das Verschachteln gemacht habe, als auch der Kommentar "korrigieren" (jetzt gelöscht) waren falsch, und separat meine Behauptung, dass das Ausprobieren aller möglichen Verschachtelungen eine optimale Lösung ergeben muss war auch falsch (ich gebe ein einfaches Gegenbeispiel unten). Zum Schluss mein Vorschlag zu setzenx+=zj und iterieren oder die Strahlensuche verwenden ist eigentlich auch nicht hilfreich: Welche Antwort auch immer dadurch erzeugt werden könnte und die Anwendung von Aryabhatas DP kann niemals besser sein als die Verwendung des Originals x+, da es lediglich die Größe des Lösungssatzes reduziert, aus dem der DP auswählen kann. Es tut uns leid! Hoffentlich enthält die verbesserte Version unten keine weiteren Probleme ...

Ich habe auch zwei Fehler in Aryabhatas DP bemerkt . Glücklicherweise können beide leicht repariert werden (siehe meine Kommentare zu diesem Beitrag).

Eine heuristische Lösung mit zufälligen Verschachtelungen

Wenn Sie nicht unbedingt die kürzeste Teilsequenz benötigen, können Sie die Tatsache verwenden, dass, wenn eine Zeichenfolge s ist eine Folge von einigen xidann ist es auch eine Folge jeder möglichen Verschachtelung aller Stringsxi. Drehen Sie dies um, wenns ist keine Folge einer bestimmten Verschachtelung aller Zeichenketten xi, Dann ist es keine Folge von jedem einzelnenxi.

Sie können also viele verschiedene Möglichkeiten ausprobieren, um das zufällig zu verschachteln n Saiten xi in eine einzelne Zeichenfolge und für jede solche Verschachtelung yjSuchen Sie nach der kürzesten Folge zj von x+ das vermeidet, eine Folge von zu sein yjVerwenden Sie den netten DP-Algorithmus von Aryabhata für den Fall mit zwei Zeichenfolgen und wählen Sie den gewünschten auszj ist über alle von Ihnen versuchten Verschachtelungen am kürzesten.

Vorsichtsmaßnahme: Keine Garantie für Optimalität, auch wenn wir alle Verschachtelungen versuchen

Überraschenderweise (zumindest für mich) ist es nicht garantiert, dass Sie die optimale Lösung finden, selbst wenn Sie das obige Verfahren für alle möglichen Verschachtelungen wiederholen: Betrachten Sie den Fall, in dem x+=aaa, n=2, und x1=x2=a. Dannaa ist eine optimale Lösung mit Länge 2, aber die kürzeste Lösung, die durch Ausprobieren aller Verschachtelungen von gefunden wird x1 und x2 ist aaamit der Länge 3.

j_random_hacker
quelle