Finden Sie die längste gemeinsame Teilzeichenfolge in C++

1. Längste gemeinsame Teilzeichenfolge
2. Problemformulierung des längsten gemeinsamen Teilstrings

In diesem Artikel besprechen wir das am längsten verbreitete Teilstring-Problem und seine Lösung mit dynamischer Programmierung in C++.

Längste gemeinsame Teilzeichenfolge

Der längste gemeinsame Teilstring (LCS) ist ein bekanntes Problem in der Informatik. Eine Teilzeichenfolge mit maximaler Länge in zwei oder mehr Zeichenfolgen ist die längste gemeinsame Teilzeichenfolge.

Betrachten Sie beispielsweise die folgenden drei Zeichenfolgen:

1. XYXYZ
2. YXYZX
3. XYZYX

Der längste gemeinsame Teilstring dieser drei Strings ist XYZ. In diesen drei Strings gibt es weitere gemeinsame Teilstrings wie X, XY, Y, YX, YZ und Z; Der längste gemeinsame Teilstring ist jedoch nur XYZ.

Abbildung 1 zeigt den längsten gemeinsamen Teilstring der oben genannten drei Strings:

Problemformulierung des längsten gemeinsamen Teilstrings

Betrachten Sie zwei Strings, S1 und S2, mit den Längen m bzw. n, um den genauen Teilstring von S1 und S2 mit der maximalen Länge zu finden.

Wir werden zwei Lösungen für dieses Problem vorstellen:

1. Eine einfache Lösung
2. Dynamische Programmierlösung

Eine einfache Lösung

Im Folgenden finden Sie die Schritte, um die längste gemeinsame Teilzeichenfolge aus zwei Zeichenfolgen mithilfe der einfachen Lösung zu finden:

Diese Lösung kann die längste gemeinsame Teilzeichenfolge finden; Dies wird jedoch einige Zeit in Anspruch nehmen. Schauen wir uns also die dynamische Programmierlösung an, um das gleiche Ziel in kürzerer Zeit zu erreichen.

Finden Sie die längste gemeinsame Teilzeichenfolge durch dynamische Programmierung

Wir können die dynamische Programmierung (DP) verwenden, um den längsten gemeinsamen Teilstring (LCS) aus zwei Strings zu finden. Es folgt der Pseudocode zum Finden der längsten gemeinsamen Teilzeichenfolge unter Verwendung des dynamischen Programmieransatzes:

function Longest_Common_Substring(S1[1..m], S2[1..n])
    DP_Matrix = array(1..m, 1..n)
    len = 0
    result_substring = {}
    for i = 1..m
        for j = 1..n
            if S1[i] == S2[j]
                if i = 1 or j = 1
                    DP_Matrix[i, j] = 1
                else
                    DP_Matrix[i, j] = DP_Matrix[i − 1, j − 1] + 1
                if DP_Matrix[i, j] > len
                    len = DP_Matrix[i, j]
                    result_substring = {S1[i − len + 1..i]}
                else if DP_Matrix[i, j] == len
                    result_substring = result_substring ∪ {S1[i − len + 1..i]}
            else
                DP_Matrix[i, j] = 0
    return result_substring

Die obige Lösung benötigt quadratische (d. h. $\mathcal{O}(mn)$) Zeitkomplexität, um den längsten gemeinsamen Teilstring zu berechnen. Die Lösung ist optimal und garantiert immer die längste Teilübereinstimmung.

Hinweis: Die Arrays in Pseudocodes beginnen bei Index 1. Außerdem funktioniert dieser Algorithmus nur mit nicht leeren Strings.

Die DP_Matrix ist ein 2D-Array oder eine Matrix, die als dynamische Programmiertabelle verwendet wird, um die Teilstringlänge für die Präfixe S1[1..i] und S2[1..j] mit den Endpositionen S1[i] und S2[j].

Die Variable len dient zum Speichern der aktuell grössten result_substring-Länge, die bisher gefunden wurde. Der Teilstring wird verwendet, um den String der Länge len zu speichern.

Alle Zellen in der ersten Zeile und Spalte der DP_matrix werden auf 1 initialisiert. Eine objektive Funktion wird verwendet, um die verbleibenden Zellen zu berechnen.

Die Zielfunktion für diese Formulierung kann wie folgt dargestellt werden:

1. Für eine gegebene Zelle DP_Matrix[i,j], wenn die entsprechenden Zeichen der gegebenen Zeichenfolgensequenzen (d.h. die Zeichen bei S1[i] und S2[j]) übereinstimmen, dann fügen wir 1 auf den Wert der Zelle DP_Matrix[i-1,j-1].
   • Wenn der aktualisierte Wert der Zelle DP_Matrix[i,j] größer ist als die vorherige Länge des Teilstrings, aktualisieren Sie len mit diesem neuen Wert.
   • Speichern Sie gleichzeitig diesen neuen maximalen String in einem Hilfsstringhalter (d. h. result_substring).
2. Wenn die entsprechenden Zeichen nicht übereinstimmen (d. h. ein Nichtübereinstimmungsfall), setzen Sie die Zelle DP_Matrix[i, j] auf einen Nullwert, um anzuzeigen, dass hier nur ein neuer Teilstring beginnen kann.

Nach all den M*N-Iterationen (d. h. dem Ende der for-Schleifen) hat der result_substring einen optimal größten gemeinsamen Teilstring.

Längste übliche Lösung für die dynamische Programmierung von Teilzeichenfolgen in C++

Der folgende Code wird verwendet, um die längste gemeinsame Teilzeichenfolge aus den Zeichenfolgen mithilfe der dynamischen Programmierung in C++ zu finden.

#include <iostream>
#include <string>
using namespace std;

string Longest_Common_Substring(string Str1, string Str2) {
  string result_substring = "";
  int m = Str1.length();
  int n = Str2.length();
  int DP_Matrix[m + 1][n + 1];
  int len = 0;
  int end = 0;

  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
      if (Str1[i] == Str2[j]) {
        if ((i == 0) || (j == 0))
          DP_Matrix[i][j] = 1;
        else
          DP_Matrix[i][j] = 1 + DP_Matrix[i - 1][j - 1];

        if (DP_Matrix[i][j] > len) {
          len = DP_Matrix[i][j];
          int start = i - DP_Matrix[i][j] + 1;
          if (end == start) {
            result_substring.push_back(Str1[i]);
          } else {
            end = start;
            result_substring.clear();
            result_substring.append(Str1.substr(end, (i + 1) - end));
          }
        }
      } else {
        DP_Matrix[i][j] = 0;
      }
    }
  }
  return result_substring;
}

int main() {
  string String1, String2;
  cout << "Enter the first string: ";
  cin >> String1;
  cout << "Enter the second string: ";
  cin >> String2;
  string substring = Longest_Common_Substring(String1, String2);
  cout << "LCS of " << String1 << " and " << String2 << " is " << substring
       << " of Length " << substring.length() << endl;
  return 0;
}

Der obige Code enthält die Funktion Longest_Common_Substring, die zwei Strings (d. h. String1 und String2) als Parameter akzeptiert und ihren optimalen größten gemeinsamen Teilstring zurückgibt. Die Funktion Longest_Common_Substring verwendet die dynamische Programmiertabellenmethode, um diesen LCS zu finden.

Im obigen Code ist die DP_Matrix ein 2D-Integer-Array, das die aktuell beste Teilstringlänge für das String-Unterpaar S1[1..i] und S2[1..j] speichert. Der result_substring wird, wie in der Pseudocode-Erklärung besprochen, verwendet, um den längsten gefundenen Teilstring zu speichern.

Schauen wir uns die Ausgaben des obigen Codes für verschiedene Zeichenfolgenpaare an:

Ausgang 1:

Enter the first string: ATGCACATA
Enter the second string: GCAATGCACT
LCS of ATGCACATA and GCAATGCACT is ATGCAC of Length 6

Ausgang 2:

Enter the first string: ABCDDFA
Enter the second string: DCDDACDDF
LCS of ABCDDFA and DCDDACDDF is CDDF of Length 4

Neben dem theoretischen oder mathematischen Beweis legen die obigen Ergebnisse nahe, dass die diskutierte dynamische Programmierlösung optimal ist.