Solution optimisée en termes d'espace pour le programme LCS en C ?-C++-php.cn

Solution optimisée en termes d'espace pour le programme LCS en C ?

王林

Libérer： 2023-09-05 13:45:06

avant

855 Les gens l'ont consulté

Solution optimisée en termes despace pour le programme LCS en C ?

Ici, nous verrons une méthode d'optimisation spatiale pour le problème LCS. LCS est la sous-séquence commune la plus longue. Si les deux chaînes sont « BHHUBC » et « HYUYBZC », alors la longueur de la sous-séquence est de 4. La méthode de programmation dynamique en fait déjà partie, mais son utilisation prendra plus de place. Nous avons besoin d'un tableau d'ordre m x n, où m est le nombre de caractères dans la première chaîne et n est le nombre de caractères dans la deuxième chaîne.

Ici, nous verrons comment utiliser l'espace auxiliaire O(n). Si nous regardons l’ancienne approche, nous pouvons voir qu’à chaque itération, nous avons besoin des données de la ligne précédente. Toutes les données ne sont pas obligatoires. Donc si on fait un tableau de taille 2n, ce n'est pas un problème. Regardons l'algorithme pour comprendre cette idée.

Algorithme

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 &ndash; index, j - 1] + 1
         else
            L[index, j] := max of L[1 &ndash; index, j] and L[index, j-1]
         end if
      done
   done
   return L[index, n]
end

Copier après la connexion

Exemple

#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);
}

Copier après la connexion