LCS的空间优化解-yiteyi-C++库

给定两个字符串，求两个字符串中最长子序列的长度。

null

例如：

LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

我们讨论了一个问题典型的基于动态规划的LCS解决方案 .我们可以优化LCS问题所使用的空间。我们知道LCS问题的复发关系是

CPP

                         /* 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];                       
                         }                       

JAVA

                         class                                     GFG {                       
           
                                                 // Returns length of LCS for X[0..m-1], Y[0..n-1]                       
           
                                                 public                                     static                                     int                                     lcs(String X, String Y)                       
                                                 {                       
           
                                                 // Find lengths of two strings                       
                                                 int                                     m = X.length(), n = Y.length();                       
           
                                                 int                                     L[][] =                                     new                                     int                                     [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];                       
                                                 }                       
                         }                       
           
                         // This code is contributed by rajsanghavi9.                       

Javascript

                         <script>                       
           
                         // Dynamic Programming Java implementation of LCS problem                       
           
                         // Utility function to get max of 2 integers                       
                         function                                     max(a, b)                       
                         {                       
                                                 if                                     (a > b)                       
                                                 return                                     a;                       
                                                 else                       
                                                 return                                     b;                       
                         }                       
           
                         // Returns length of LCS for X[0..m-1], Y[0..n-1]                       
                         function                                     lcs(X, Y, m, n)                       
                         {                       
                                                 var                                     L =                                     new                                     Array(m + 1);                       
                                                 for                                     (                                     var                                     i = 0; i < L.length; i++)                       
                                                 {                       
                                                 L[i] =                                     new                                     Array(n + 1);                       
                                                 }                       
                                                 var                                     i, j;                       
                                   
                                                 /* 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                                     (i = 0; i <= m; i++)                       
                                                 {                       
                                                 for                                     (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];                       
                         }                       
           
                         // This code is contributed by akshitsaxenaa09.                       
                         </script>                       

如何求LCS的长度为O（n）辅助空间？

我们强烈建议您在继续解决方案之前单击此处并进行练习。 上述简单实现中的一个重要观察结果是，在外部循环的每次迭代中，我们只需要 来自上一行所有列的值 。因此，不需要存储DP矩阵中的所有行，我们可以一次存储两行并使用它们。这样，使用的空间将从L[m+1][n+1]减少到L[2][n+1]。下面是上述想法的实施。

C++

                         // 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-1] == 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 code                       
                         int                                     main()                       
                         {                       
                                                 string X =                                     "AGGTAB"                                     ;                       
                                                 string Y =                                     "GXTXAYB"                                     ;                       
           
                                                 printf                                     (                                     "Length of LCS is %d"                                     , lcs(X, Y));                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Code for A Space Optimized                       
                         // Solution of LCS                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns length of LCS                       
                                                 // for X[0..m - 1],                       
                                                 // Y[0..n - 1]                       
                                                 public                                     static                                     int                                     lcs(String X,                       
                                                 String Y)                       
                                                 {                       
                                   
                                                 // Find lengths of two strings                       
                                                 int                                     m = X.length(), n = Y.length();                       
                                   
                                                 int                                     L[][] =                                     new                                     int                                     [                                     2                                     ][n+                                     1                                     ];                       
                                   
                                                 // Binary index, used to index                       
                                                 // current row and previous row.                       
                                                 int                                     bi=                                     0                                     ;                       
                                   
                                                 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.charAt(i -                                     1                                     ) ==                       
                                                 Y.charAt(j -                                     1                                     ))                       
                                                 L[bi][j] = L[                                     1                                     - bi][j -                                     1                                     ] +                                     1                                     ;                       
                                   
                                                 else                       
                                                 L[bi][j] = Math.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 Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String X =                                     "AGGTAB"                                     ;                       
                                                 String Y =                                     "GXTXAYB"                                     ;                       
                                   
                                                 System.out.println(                                     "Length of LCS is "                                     +                       
                                                 lcs(X, Y));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Arnav Kr. Mandal.                       

Python3

                         # Space optimized Python                       
                         # implementation of LCS problem                       
           
                         # Returns length of LCS for                       
                         # X[0..m-1], Y[0..n-1]                       
                         def                                     lcs(X, Y):                       
                                   
                                                 # Find lengths of two strings                       
                                                 m                                     =                                     len                                     (X)                       
                                                 n                                     =                                     len                                     (Y)                       
           
                                                 L                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                                     for                                     j                                     in                                     range                                     (                                     2                                     )]                       
           
                                                 # Binary index, used to index current row and                       
                                                 # previous row.                       
                                                 bi                                     =                                     bool                       
                                   
                                                 for                                     i                                     in                                     range                                     (m):                       
                                                 # Compute current binary index                       
                                                 bi                                     =                                     i&                                     1                       
           
                                                 for                                     j                                     in                                     range                                     (n                                     +                                     1                                     ):                       
                                                 if                                     (i                                     =                                     =                                     0                                     or                                     j                                     =                                     =                                     0                                     ):                       
                                                 L[bi][j]                                     =                                     0                       
           
                                                 elif                                     (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 Code                       
                         X                                     =                                     "AGGTAB"                       
                         Y                                     =                                     "GXTXAYB"                       
           
                         print                                     (                                     "Length of LCS is"                                     , lcs(X, Y))                       
           
                         # This code is contributed by Soumen Ghosh.                       

C#

                         // C# Code for A Space                       
                         // Optimized Solution of LCS                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // Returns length of LCS                       
                                                 // for X[0..m - 1],                       
                                                 // Y[0..n - 1]                       
                                                 public                                     static                                     int                                     lcs(                                     string                                     X,                       
                                                 string                                     Y)                       
                                                 {                       
                                   
                                                 // Find lengths of                       
                                                 // two strings                       
                                                 int                                     m = X.Length, n = Y.Length;                       
                                   
                                                 int                                     [,]L =                                     new                                     int                                     [2, n + 1];                       
                                   
                                                 // Binary index, used to                       
                                                 // index current row and                       
                                                 // previous row.                       
                                                 int                                     bi = 0;                       
                                   
                                                 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 - 1] == Y[j - 1])                       
                                                 L[bi, j] = L[1 - bi,                       
                                                 j - 1] + 1;                       
                                   
                                                 else                       
                                                 L[bi, j] = Math.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 Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 string                                     X =                                     "AGGTAB"                                     ;                       
                                                 string                                     Y =                                     "GXTXAYB"                                     ;                       
                                   
                                                 Console.Write(                                     "Length of LCS is "                                     +                       
                                                 lcs(X, Y));                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by shiv_bhakt.                       

PHP

                         <?php                       
                         // Space optimized PHP implementation                       
                         // of LCS problem                       
           
                         // Returns length of LCS                       
                         // for X[0..m-1], Y[0..n-1]                       
                         function                                     lcs(                                     $X                                     ,                                     $Y                                     )                       
                         {                       
                                   
                                                 // Find lengths of two strings                       
                                                 $m                                     =                                     strlen                                     (                                     $X                                     );                       
                                                 $n                                     =                                     strlen                                     (                                     $Y                                     );                       
           
                                                 $L                                     =                                     array                                     (                                     array                                     ());                       
           
                                                 // Binary index, used to index                       
                                                 // current row and previous row.                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <=                                     $m                                     ;                                     $i                                     ++)                       
                                                 {                       
                                   
                                                 // Compute current binary index                       
                                                 $bi                                     =                                     $i                                     & 1;                       
           
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <=                                     $n                                     ;                                     $j                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $i                                     == 0 ||                                     $j                                     == 0)                       
                                                 $L                                     [                                     $bi                                     ][                                     $j                                     ] = 0;                       
           
                                                 else                                     if                                     (                                     $X                                     [                                     $i                                     - 1] ==                                     $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 code                       
                         $X                                     =                                     "AGGTAB"                                     ;                       
                         $Y                                     =                                     "GXTXAYB"                                     ;                       
           
                         echo                                     "Length of LCS is : "                                     ,                       
                                                 lcs(                                     $X                                     ,                                     $Y                                     );                       
           
                         // This code is contributed by Ryuga                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript Code for A Space Optimized Solution of LCS                       
                                   
                                                 // Returns length of LCS                       
                                                 // for X[0..m - 1],                       
                                                 // Y[0..n - 1]                       
                                                 function                                     lcs(X, Y)                       
                                                 {                       
                                   
                                                 // Find lengths of two strings                       
                                                 let m = X.length, n = Y.length;                       
                                   
                                                 let L =                                     new                                     Array(2);                       
                                                 for                                     (let i = 0; i < 2; i++)                       
                                                 {                       
                                                 L[i] =                                     new                                     Array(n + 1);                       
                                                 for                                     (let j = 0; j < n + 1; j++)                       
                                                 {                       
                                                 L[i][j] = 0;                       
                                                 }                       
                                                 }                       
                                   
                                   
                                                 // Binary index, used to index                       
                                                 // current row and previous row.                       
                                                 let bi=0;                       
                                   
                                                 for                                     (let i = 0; i <= m; i++)                       
                                                 {                       
                                   
                                                 // Compute current binary index                       
                                                 bi = i & 1;                       
                                   
                                                 for                                     (let j = 0; j <= n; j++)                       
                                                 {                       
                                                 if                                     (i == 0 || j == 0)                       
                                                 L[bi][j] = 0;                       
                                   
                                                 else                                     if                                     (X[i - 1] ==                       
                                                 Y[j - 1])                       
                                                 L[bi][j] = L[1 - bi][j - 1] + 1;                       
                                   
                                                 else                       
                                                 L[bi][j] = Math.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];                       
                                                 }                       
                                   
                                                 let X =                                     "AGGTAB"                                     ;                       
                                                 let Y =                                     "GXTXAYB"                                     ;                       
           
                                                 document.write(                                     "Length of LCS is "                                     +                       
                                                 lcs(X, Y));                       
           
                         </script>                       

输出：

Length of LCS is 4

时间复杂性： O（m*n） 辅助空间： O（n）

这篇文章是有贡献的 希瓦姆·米塔尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章