时间戳

首页 > 解决方案 > 最长公共子序列（LCS）直觉

string - 最长公共子序列（LCS）直觉

问题描述

LCS 代码的递归版本看起来像这样（m，n 分别是字符串 X 和 Y 的长度）

    int lcs( char[] X, char[] Y, int m, int n ) { 
      if (m == 0 || n == 0) 
        return 0; 
      if (X[m-1] == Y[n-1]) 
        return 1 + lcs(X, Y, m-1, n-1); 
      else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
    }

我注意到这个算法从末尾删除字符串的字符并创建原始两个字符串的各种子字符串，然后尝试寻找匹配项。

我不明白的是，因为它只考虑某些子字符串而不是所有可能的子序列，这个算法如何保证提供正确的结果？这背后是否有逻辑/数学/直观的证明？

标签： stringalgorithmrecursiondynamic-programminglcs

解决方案

当最后一个字符相同时，它会计算 lcs( X, Y, m-1, n-1) 。

或者

当字符不同时，它会计算 lcs( X, Y, m-1,n ) 和 lcs( X, Y, m, n-1) 。

所以它涵盖了所有可能的解决方案。

如果长度为 0。则 lcs 为 0。如果最后（或第一个）项目相同，则 lcs 为 1 + lcs(X,Y,m-1,n-1) 此子句通过添加来减少问题lcs 的共同元素，并找到 2 个较短字符串中较小的 lcs。

最后最长的子序列是

lcs(X, Y, m-1, n)

或者

lcs(X, Y, m, n-1)

所以当它被要求计算 lcs("abce", "bghci", 4, 5);

if( m(4) == 0 || n(5) == 0 ) // evaluates to false
if( X[3]('e')  == Y[4] ) // evaluates to false
return max( lcs( "abc", "bghci", 3, 5 ),   // These two recursive calls
            lcs( "abce", "bghc", 4, 4 ) ); // cover the whole problem space

例如

(A) lcs( "abce", "bghci" ) =>  (B) lcs( "abc", "bghci" ) 
                               (C) lcs( "abce", "bghc" )
(B) lcs( "abc",  "bghci" ) =>  (D) lcs( "ab",   "bghci" ) 
                               (E) lcs( "abc",  "bghc" )
(C) lcs( "abce", "bghc" )  =>  (F) lcs( "abc",  "bghc" )
                               (G) lcs( "abce", "bgh"  )
(D) lcs( "ab"  , "bghci")  =>  (H) lcs( "a" ,   "bghci")
                               (I) lcs( "ab"  , "bghc" )
(E) lcs( "abc", "bghc" )   =>  1 + (J) lcs( "ab"  , "bgh")
(F) lcs( "abc", "bghc" )   =>  1 + (K) lcs( "ab"  , "bgh")
(G) lcs( "abce", "bgh" )   =>  (L) lcs( "abc", "bgh" )
                               (M) lcs( "abce", "bg" )
(H) lcs( "a", "bghci")     =>      lcs( "",    "bghci" )  (0)
                               (N) lcs( "a",   "bghc" )
(I) lcs( "ab", "bghc")     =>  (O) lcs( "a",   "bghc" )
                               (P) lcs( "ab",  "bgh" )
(J) lcs( "ab", "bgh" )     =>  (Q) lcs( "a",   "bgh" )
                               (R) lcs( "ab",  "bg" )
(K) lcs( "ab", "bgh" )     =>  (S) lcs( "a",   "bgh" )
                               (T) lcs( "ab",  "bg" )
(L) lcs( "abc", "bgh" )    =>  (U) lcs( "ab",  "bg" )
                               (V) lcs( "abc", "bg" )
(M) lcs( "abce", "bg" )    =>  (W) lcs( "abc", "bg" )
                               (X) lcs( "abce","b" )
(N) lcs( "a",  "bghc")     =>      lcs( "",    "bghc" )   (0)
                               (Y) lcs( "a",   "bgh" )
(O) lcs( "a", "bghc" )     =>      lcs( "",    "bghc" )   (0)
                                   lcs( "a"    "bgh" )
(P) lcs( "ab", "bgh" )     =>  (Z) lcs( "a",   "bgh" )
                              (AA) lcs( "ab",  "bg" )
(Q) lcs( "a",  "bgh" )     =>      lcs( "",    "bgh")     (0)
                              (AB) lcs( "a",   "bg")
(R) lcs( "ab", "bg" )      => (AC) lcs( "a",   "bg")
                              (AD) lcs( "ab",  "b" )
(S) lcs( "a", "bgh" )      =>      lcs( "",    "bgh")     (0)
                              (AE) lcs( "a",   "bg" )
(T) lcs( "ab", "bg" )      => (AF) lcs( "a",   "bg" )
                              (AG) lcs( "ab",  "b" )
(U) lcs( "ab", "bg" )      => (AH) lcs( "a",   "bg" )
                              (AI) lcs( "ab",  "b" )
(V) lcs( "abc","bg" )      => (AJ) lcs( "ab",  "bg" )
                           => (AK) lcs( "abc", "b" )
(W) lcs( "abc","bg" )      => (AL) lcs( "ab",  "bg" )
                              (AM) lcs( "abc", "b"  )
(X) lcs( "abce", "b")      => (AN) lcs( "abc", "b" )
                                   lcs( "abce", "" )     (0)
(Y) lcs( "abce", "b")      => (AO) lcs( "abc", "b" )
                                   lcs( "abce", "" )     (0)
(Z) lcs( "a", "bgh")       =>      lcs( "",    "bgh" )   (0)
                              (AP) lcs( "a",   "bg" )
(AA)lcs( "ab", "bg")       => (AQ) lcs( "a",   "bg" )
                              (AR) lcs( "ab",  "b" )
(AB)lcs( "a",  "bg")       =>      lcs( "",    "bg" )    (0)
                              (AS) lcs( "a",   "b" )
(AC)lcs( "a",  "bg")       =>      lcs( "",    "bg")     (0)
                              (AT) lcs( "a",   "b")
(AD)lcs( "ab", "b")        =>  1 + lcs( "a",   "" )      (1)
(AE)lcs( "a",  "bg")       =>      lcs( "",    "bg")
                              (AU) lcs( "a",   "b" )
(AF)lcs( "a",  "bg")       =>      lcs( "",    "bg")     (0)
                              (AV) lcs( "a",   "b")
(AG)lcs( "ab", "b" )       =>  1 + lcs( "a",   "" )      (1)
(AH)lcs( "a",  "bg")       =>      lcs( "",    "bg")     (0)
                              (AW) lcs( "a",   "b" )
(AI)lcs( "ab", "b")        =>  1 + lcs( "a",   "" )      (1)
(AJ)lcs( "ab", "bg")       => (AX) lcs( "a",   "bg")
(AK)lcs( "abc", "b")       => (AY) lcs( "ab",  "b")
                                   lcs( "abc", "b")      (0)
(AL)lcs( "ab", "bg")       => (AZ) lcs( "a",   "bg")
                              (BA) lcs( "ab",  "b")
(AM)lcs( "abc", "b")       => (BB) lcs( "ab",  "b")
                                   lcs( "abc", "" )      (0)
(AN)lcs( "abc", "b")       => (BC) lcs( "ab",  "b")
                                   lcs( "abc", "" )      (0)
(AO)lcs( "abc", "b")       => (BD) lcs( "ab",  "b")
                                   lcs( "abc", "" )      (0)
(AP)lcs( "a", "bg")        =>      lcs( "",    "bg")     (0)
                              (BE) lcs( "a",   "b") 
(AQ)lcs( "a", "bg")        =>      lcs( "",    "bg")     (0)
                              (BF) lcs( "a",   "b") 
(AR)lcs( "ab", "b")        => 1 +  lcs( "a", "" )        (1)
(AS)lcs( "a",  "b")        =>      lcs( "",  "b")        (0)
                                   lcs( "a", "" )        (0)
(AT)lcs( "a", "b" )        as (AS)
(AU)lcs( "a", "b" )        as (AS)
(AV)lcs( "a", "b")         as (AS)
(AW)lcs( "a", "b")         as (AS)
(AX)lcs( "a", "bg")        =>      lcs( "", "bg")        (0)
                              (BG) lcs( "a", "b")
(AY)lcs( "ab", "b")        => 1 +  lcs( "a", "" )        (1)
(AZ)lcs( "a",  "bg")       =>      lcs( "", "bg")        (0)
                              (BH) lcs( "a", "b")
(BA)lcs( "ab", "b")        => 1 +  lcs( "a", "" )        (1)
(BB)lcs( "ab", "b")        => 1 +  lcs( "a", "" )        (1)
(BC)lcs( "ab", "b")        => 1 +  lcs( "a", "" )        (1)
(BD)lcs( "ab", "b")        => 1 +  lcs( "a", "" )        (1)
(BE)lcs( "a",  "b")        as (AS)
(BF)lcs( "a",  "b")        as (AS)
(BG)lcs( "a",  "b")        as (AS)

所以 2 的 lcs 来自下面的调用栈....

lcs( "abcde", "bghci")               // (A)
  lcs( "abcd", "bghci" )             // (B)
    lcs( "abc",  "bghc" )            // (E)
      1 + lcs( "ab", "bgh" )         // (J)
        lcs( "ab",  "bg" )           // (R)
          lcs( "ab",  "b" )          // (AD)
            1 + lcs( "a",   "" )

答案为 2。如您所见，它测试了更多组合。

我不明白的是，因为它只考虑某些子字符串而不是所有可能的子序列，

该算法的技巧是注意如果第一个（或最后一个字符相同），那么最长的公共子序列是 1 + 2 个较短字符串的 lcs。诸如归纳证明或矛盾证明之类的东西可以帮助您证明工作分工对于涵盖所有可能的替代方案是必要且充分的。

从我的构建中可以看出，它在计算 lcs 时多次考虑了许多替代方案，因此它不是一个非常有效的算法。

推荐阅读