Platzoptimierte Lösung für LCS im C-Programm?

Hier sehen wir eine räumliche Optimierungsmethode für das LCS-Problem. LCS ist die längste gemeinsame Teilsequenz. Wenn die beiden Zeichenfolgen „BHHUBC“ und „HYUYBZC“ sind, beträgt die Länge der Teilsequenz 4. Die dynamische Programmiermethode ist bereits eine davon, aber die Verwendung der dynamischen Programmiermethode wird mehr Platz beanspruchen. Wir benötigen eine Tabelle der Ordnung m x n, wobei m die Anzahl der Zeichen in der ersten Zeichenfolge und n die Anzahl der Zeichen in der zweiten Zeichenfolge ist.

Hier erfahren Sie, wie Sie den O(n)-Hilfsraum nutzen. Wenn wir uns den alten Ansatz ansehen, können wir erkennen, dass wir in jeder Iteration die Daten aus der vorherigen Zeile benötigen. Nicht alle Daten sind erforderlich. Wenn wir also eine Tabelle der Größe 2n erstellen, ist das kein Problem. Schauen wir uns den Algorithmus an, um diese Idee zu verstehen.

Algorithmus

lcs_problem(X, Y) -

begin
   m := length of X
   n := length of Y
   define table of size L[2, n+1]
   index is to point 0th or 1st row of the table L.
   for i in range 1 to m, do
      index := index AND 1
      for j in range 0 to n, do
         if i = 0 or j = 0, then
            L[index, j] := 0
         else if X[i - 1] = Y[j - 1], then
            L[index, j] := L[1 – index, j - 1] + 1
         else
            L[index, j] := max of L[1 – index, j] and L[index, j-1]
         end if
      done
   done
   return L[index, n]
end

Beispiel

#include <iostream>
using namespace std;
int lcsOptimized(string &X, string &Y) {
   int m = X.length(), n = Y.length();
   int L[2][n + 1];
   bool index;
   for (int i = 0; i <= m; i++) {
      index = i & 1;
      for (int j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[index][j] = 0;
         else if (X[i-1] == Y[j-1])
            L[index][j] = L[1 - index][j - 1] + 1;
         else
            L[index][j] = max(L[1 - index][j], L[index][j - 1]);
      }
   }
   return L[index][n];
}
int main() {
   string X = "BHHUBC";
   string Y = "HYUYBZC";
   cout << "Length of LCS is :" << lcsOptimized(X, Y);
}

Ausgabe

Length of LCS is :4

Das obige ist der detaillierte Inhalt vonPlatzoptimierte Lösung für LCS im C-Programm?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!