LCS - Longest Common Subsequence

• LCS 算法是 diff 算法的基础
• LCS 算法也是理解 Editing Distance 算法的基础
• LCS 算法是动态规划算法的典型实例
  • 动态规划 - Dynamic Programming
• LeetCode-1143: Longest Common Subsequence
• LeetCode-516: Longest Palindromic Subsequence
  • 最长回文子序列
  • 可以看作是与自身逆序字符串的 LCS

LCS 递归算法

int LCS(char *text_a, int n, char *text_b, int m){
  if( n<=0 || m<=0 ){
    return 0;
  }else if( text_a[n-1] == text_b[m-1] ){
    return 1 + LCS(text_a, n-1, text_b, m-1);
  }else{
    return max(
      LCS(text_a, n,   text_b, m-1),
      LCS(text_a, n-1, text_b, m)
    );
  }
}

LCS 递归算法的事件复杂度是 2^n

LCS 动态规划算法

LCS 递归算法的问题是中间有很多重复的计算。

动态规划算法如下

int LCS(char *text_a, int n, char *text_b, int m){
   int lut[n][m];  // Lookup Table

   for(int i=0; i<n; i++){
     for(int j=0; j<m; j++){
       if( text_a[i] == text_b[j] ){
         lut[i][j] = lut[i-1][j-1] + 1;
       }else{
         lut[i][j] = max(lut[i][j-1], lut[i-1][j]);
       }
    } // end for j
  } // end for i

  return lut[n-1][m-1];
}

LCS 动态规划算法的事件复杂度是 n*m

处理边界值

上面的算法在处理第一行和第一列这样的边界情况时，没有进行特殊处理。可以通过人为地增加一行和一列的方法，消除这种特殊处理的必要性。

int LCS(char *text_a, int n, char *text_b, int m){
   int lut[n+1][m+1];  // Lookup Table
   for(int i=0; i<=n; i++) lut[i][0] = 0;
   for(int j=0; j<=m; j++) lut[0][j] = 0;

   for(int i=1; i<=n; i++){
     for(int j=1; j<=m; j++){
       if( text_a[i-1] == text_b[j-1] ){
         lut[i][j] = lut[i-1][j-1] + 1;
       }else{
         lut[i][j] = max(lut[i][j-1], lut[i-1][j]);
       }
    } // end for j
  } // end for i

  return lut[n][m];
}

LCS Backtrace

上面的 LCS 算法只是返回了 LCS 的长度。

通过逆向回溯上面的 Lookup Table 可以得到具体的 LCS 序列。

LCS 与 Diff

在确定了 LCS 序列的情况下，连个相邻的 LCS 序列元素中间的部分，就是不同的地方。

这种不同可以划分为三类：

1. 插入 / Insert
2. 删除 / Delete
3. 修改 / Replace

LCS 与 Editing Distance

把 Diff 的结果量化，可以看作是一种 Editing Distance —— 编辑距离。

是一种 Minimum Editing Distance， 也叫做 Levenshtein Distance。

Minimum Editing Distance 和 Longest Common Sequence 可以看作是同一个问题的一体两面。

Editing Distance 递归算法

int editDistance(char *text_a){
  if( text_a[i] == text_b[j] ){
    return editDistance(text_a, n-1, text_b, m-1) 
  }else{
    return min(
      editDistance(text_a, n, text_b, m-1) ,  // Remove
      editDistance(text_a, n-1, text_b, m) ,  // Insert
      editDistance(text_a, n-1, text_b, m-1)  // Replace
    );
  }
}

文本相似度

可以用 Editing Distance 来衡量连个字符串的相似度。