Ist diese Methode der längsten gemeinsamen Teilzeichenfolge korrekt?

Question

Ich habe einen Algorithmus dafür gefunden Längster gemeinsamer Teilstring.Dies geschieht normalerweise mit dynamic programming, unter Verwendung eines 2D-Arrays der Größe mxn Wo m Und n sind Längen der beiden betrachteten Zeichenfolgen.

Ich werde die folgende Matrix für die beiden Zeichenfolgen erstellen.

M[i][j] = 1 if s1[i]==s2[j] else 0.

Wenn die Zeichenfolgen beispielsweise wie folgt lauten: abcxy Und pqaabx

Die Matrix sieht wie folgt aus:

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

Nun suche ich nach einer maximalen kontinuierlichen Folge von 1s in jeder Diagonale, die von links oben nach rechts unten verläuft.

Der Maximalwert unter diesen wird die Antwort sein.

Ich kann die obige Operation ausführen, ohne das Array explizit zu verwenden.Die Zeitkomplexität ist immer noch vorhanden O(M*N).Es ist also kein Speicher erforderlich.

Kann mir jemand zeigen, wo ich falsch liege?

Answer 1

Deine Methode ist richtig.Nehmen wir zum Beweis an, dass die längste gemeinsame Teilzeichenfolge für S1 und S2 aus S1[i..j] und S2[p..q] stammt.Dies impliziert s1 [i+k] = s2 [p+k

Diese liegen alle ausgehend von (i,p) auf der Diagonalen.

Die dynamische Programmierlösung macht das Gleiche, aber anstatt zuerst die Tabelle zu berechnen und diagonale Pfade zu durchlaufen, berechnet sie die Tabelle abhängig von ihrem diagonalen übergeordneten Element und davon, ob sie übereinstimmen oder nicht.

BEARBEITET

Zu Ihrem Kommentar zur Wikipedia-Lösung mit zusätzlichem Speicher.Es dient nur der Klarheit.Im Prinzip benötigen Sie in der Wikipedia-Lösung nur zwei Zeilen der Matrix und behalten die aktuelle maximale Anzahl in einer Variablen bei.Dies ist für jeden (i,j)ten Eintrag in der Matrix korrekt

M(i,j) = 1 + M(i-1, j-1) (wenn s1[i] == s2[j])

Wie Sie sehen, hängen die Elemente der aktuellen Zeile nur von den Elementen der unmittelbar oberen Zeile ab.

Answer 2

Ihr Algorithmus ist korrekt, aber der Standard-DP-Ansatz eliminiert Ihre zweite Phase und macht die Lösung einfacher.

Anstatt boolesche Werte zu markieren und dann die Diagonalen zu scannen, um nach den längsten Sequenzen zu suchen, können Sie die Diagonallängen beim Erstellen der Matrix berechnen – es ist nur ein Durchgang erforderlich.

Hinsichtlich der zeitlichen und räumlichen Komplexität sind beide Lösungen O(NxM).Ihre Lösung kann etwas Speicher sparen, wenn Sie eine Bitmatrix-Darstellung verwenden, während die andere Lösung wahrscheinlich etwas schneller ist.