神刀安全网

A Space Optimized Solution of LCS

Given two strings, find the length of longest subsequence present in both of them.

Examples:

LCS for input Sequences “ ABCDGH ” and “ AEDFHR ” is “ ADH ” of length 3 .

LCS for input Sequences “ AGGTAB ” and “ GXTXAYB ” is “ GTAB ” of length 4 .

We have discussed typical dynamic programming based solution for LCS . We can optimize space used by lcs problem. We know recurrence relation of LCS problem is

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs(string &X, string &Y) {     int m = X.length(), n = Y.length();     int L[m+1][n+1];      /* Following steps build L[m+1][n+1] in bottom up        fashion. Note that L[i][j] contains length of        LCS of X[0..i-1] and Y[0..j-1] */     for (int i=0; i<=m; i++)     {         for (int j=0; j<=n; j++)         {             if (i == 0 || j == 0)                 L[i][j] = 0;              else if (X[i-1] == Y[j-1])                 L[i][j] = L[i-1][j-1] + 1;              else                 L[i][j] = max(L[i-1][j], L[i][j-1]);         }     }      /* L[m][n] contains length of LCS for X[0..n-1] and        Y[0..m-1] */     return L[m][n]; }

Space Optimized:
One important observation in above implementation is, in each iteration of outer loop we only, need values from all columns of previous row . So there is no need of storing all rows in our DP matrix, we can just store two rows at a time and use them, in that way used space will reduce from L[m+1][n+1] to L[2][n+1]. Below is C++ implementation of this idea.

/* Space optimized C++ implementation of LCS problem */ #include<bits/stdc++.h> using namespace std;  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs(string &X, string &Y) {     // Find lengths of two strings     int m = X.length(), n = Y.length();      int L[2][n+1];      // Binary index, used to index current row and     // previous row.     bool bi;      for (int i=0; i<=m; i++)     {         // Compute current binary index         bi = i&1;          for (int j=0; j<=n; j++)         {             if (i == 0 || j == 0)                 L[bi][j] = 0;              else if (X[i] == Y[j-1])                 L[bi][j] = L[1-bi][j-1] + 1;              else                 L[bi][j] = max(L[1-bi][j], L[bi][j-1]);         }     }      /* Last filled entry contains length of LCS        for X[0..n-1] and Y[0..m-1] */     return L[bi][n]; }  /* Driver program to test above function */ int main() {     string X = "AGGTAB";     string Y = "GXTXAYB";      printf("Length of LCS is %d/n", lcs(X, Y));      return 0; }

Output:

Length of LCS is 4

Time Complexity : O(m*n)Auxiliary Space : O(n)

This article is contributed Shivam Mittal . Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » A Space Optimized Solution of LCS

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮