算法设计与分析[0011] Dynamic Programming(III)(Longest Common Subsequence)

  子序列和子字符串的不同之处在于,子序列不需要是原序列上连续的字符。对于 Longest Common Substring 以及 Longest Common Subsequence 这类题目,大多数需要用到 DP 的思想,其中,状态转移是关键。

最长公共子字符串

Given two strings, find the longest common substring.
Return the length of it.

  • Example
     Given A = “ABCD”, B = “CBCE”, return 2.
  • $L(idxA, idxB)$:以 $A[idxA]$ 和 $B[idxB]$ 结尾的相同子字符串的最长长度。最长公共子字符串必然存在所有情况中以 A 序列中某个字符结尾,以 B 序列中某个字符结尾的一种情况,所以取所有可能情况中的最大值即为 Longest Common Substring 的长度。
    • 因为要求子串连续,所以对于 $A_{idxA}$ 与 $B_{idxB}$ 来讲,它们要么与之前的公共子串构成新的公共子串;要么就是不构成公共子串。
      $$ L(idxA, idxB) = \begin{cases}
      if(idxA==0||idxB==0): \begin{cases} 1, A[idxA]==B[idxB] \cr 0, others \end{cases} \cr
      else-if(A[idxA]==B[idxB]): L(idxA-1, idxB-1) + 1 \cr
      else: 0
      \end{cases}
      $$
    • 上述过程的示例图如下,可以看出只有对角线方向上的长度延伸,长度不能保留。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      class Solution {
      public:
      /**
      * @param A, B: Two string.
      * @return: the length of the longest common substring.
      */
      int longestCommonSubstring(string &A, string &B) {
      int lenA = A.length();
      int lenB = B.length();
      if(lenA==0 || lenB==0) {
      return 0;
      }
      // L[idxA][idxB]: the largest length of LCS ending with A[idxA] and B[idxB]
      int L[lenA][lenB];
      for(int idxB=0; idxB<lenB; idxB++) {
      L[0][idxB] = B[idxB]==A[0]? 1 : 0;
      }
      for(int idxA=0; idxA<lenA; idxA++) {
      L[idxA][0] = A[idxA]==B[0]? 1 : 0;
      }

      for(int idxA=1; idxA<lenA; idxA++){
      for(int idxB=1; idxB<lenB; idxB++){
      L[idxA][idxB] = A[idxA]==B[idxB]? L[idxA-1][idxB-1]+1 : 0;
      }
      }

      int maxLen = 0;
      int maxLenIdx = -1;
      for(int idxA=0; idxA<lenA; idxA++){
      for(int idxB=0; idxB<lenB; idxB++){
      if(L[idxA][idxB] > maxLen) {
      maxLen = L[idxA][idxB];
      maxLenIdx = idxA;
      }
      }
      }
      return maxLen;
      }
      };
  • 提取最长公共子串
    • 使用变量 maxLenIdx 记录最长公共子串(长度 maxLen )对应的结尾字符下标(序列 A/B 都可以),回退获取 maxLen 个字符即可。

最长公共子序列

Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.

  • Example
     For “ABCD” and “EDCA”, the LCS is “A” (or “D”, “C”), return 1.
     For “ABCD” and “EACB”, the LCS is “AC”, return 2.
  • $L(idxA, idxB)$:以 $A_{idxA}$ 结尾的子串($A[0, 1, …, idxA], 0 \leq idxA \lt len_A$) 和 $B_{idxB}$ 结尾的子串($B[0, 1, …, idxB], 0 \leq idxB \lt len_B$)最长公共子序列的长度。自然地,$L(len_A-1, len_B-1)$ 即为所求的最长公共子序列长度。
  • 与子串不同,子序列可以是不连续的。
    • $L(idxA, idxB)$ 与 $L(idxA-1, idxB-1)$ 两者其实只差 $A_{idxA}$ 和 $B_{idxB}$ 这一对字符。
    • 如果 $A_{idxA}$ 和 $B_{idxB}$ 相同,那么就只要在以 $A_{idxA}$ 和以 $B_{idxB}$ 结尾的两个子串的最长公共子序列之后添上这个相同字符即可,这样就可以让长度增加一位。
    • 如果 $A_{idxA}$ 和 $B_{idxB}$ 不同,两个子串在末尾添加一个字符后最长公共子序列并不能得到延伸。考虑到 $A_{idxA}$ 可能与 $B_{idxB-1}$ 相同或者 $B_{idxB}$ 会与 $A_{idxA-1}$ 相同,没能延伸的最长公共子序列只能在 $L(idxA, idxB-1)$ 和 $L(idxA-1, idxB)$ 存在,取更长的那个。
    • 结合边界限制,最终得到的状态转移方程如下:
      $$ L(idxA, idxB) = \begin{cases}
      if(idxA==0): \begin{cases} 1, B[idxB]==A[0] \cr L(0, idxB-1), others \end{cases} \cr
      else·if(idxB==0): \begin{cases} 1, A[idxA]==B[0] \cr L(idxA-1, 0), others \end{cases} \cr
      else·if(A[idxA]==B[idxB]): L(idxA-1, idxB-1) + 1 \cr
      else: max(L(idxA, idxB-1), L(idxA-1, idxB))
      \end{cases}
      $$
    • 上述过程的示例图如下,可以看出同样只有对角线方向上的长度延伸,不过长度可以在 上→下左→右 方向上得到保留。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      #define max(a,b) (a>b?a:b)
      class Solution {
      public:
      /**
      * @param A, B: Two strings.
      * @return: The length of longest common subsequence of A and B.
      */
      int longestCommonSubsequence(string A, string B) {
      int lenA = A.length();
      int lenB = B.length();
      if(lenA==0 || lenB==0) {
      return 0;
      }
      // L[idxA][idxB]: the length of the LCS ending with A[idxA] and B[idxB]
      int L[lenA][lenB];
      // for recording LCS's tail element index
      int maxLen = 0, maxLenIdxA = 0, maxLenIdxB = 0;

      L[0][0] = A[0]==B[0]? 1 : 0;
      for(int idxB=1; idxB<lenB; idxB++) {
      L[0][idxB] = B[idxB]==A[0]? 1 : L[0][idxB-1];

      // for recording LCS's tail element index
      if(L[0][idxB] > maxLen) {
      maxLen = L[0][idxB];
      maxLenIdxB = idxB;
      }
      }
      for(int idxA=1; idxA<lenA; idxA++) {
      L[idxA][0] = A[idxA]==B[0]? 1 : L[idxA-1][0];

      // for recording LCS's tail element index
      if(L[idxA][0] > maxLen) {
      maxLen = L[idxA][0];
      maxLenIdxA = idxA;
      }
      }

      for(int idxA=1; idxA<lenA; idxA++) {
      for(int idxB=1; idxB<lenB; idxB++) {
      if(A[idxA] == B[idxB]) {
      L[idxA][idxB] = L[idxA-1][idxB-1] + 1;
      }
      else {
      L[idxA][idxB] = max(L[idxA][idxB-1], L[idxA-1][idxB]);
      }

      // for recording LCS's tail element index
      if(L[idxA][idxB] > maxLen) {
      maxLen = L[idxA][idxB];
      maxLenIdxA = idxA;
      maxLenIdxB = idxB;
      }
      }
      }
      return L[lenA-1][lenB-1];
      }
      };
  • 提取最长公共子序列
    • 使用变量 maxLen 记录最长公共子序列的长度,并通过变量 maxLenIdxAmaxLenIdxB 记录该最长长度序列末尾字符对应的序列 A 和序列 B 中的字符下标。
    • 在序列 A 和 B 中分别从下标 maxLenIdxAmaxLenIdxB 向左挪动,找出 maxLen 个相同字符,即为提取的最长公共子序列。
    • 如何在序列 A 和 B 中向左挪动呢?
      • A[maxLenIdxA]==B[maxLenIdxB],当前字符相同,同时左挪(因为公共子序列的特点,此时二者肯定均为到达边界):maxLenIdxA-- & maxLenIdxB--
      • A[maxLenIdxA]!=B[maxLenIdxB],当前字符不相同
        • 有挪动到边界(0)的,只能挪动另一个还没到边界的;假如同时挪动到边界,由于 maxLen 的准确性,说明已经提取出最长公共子序列。
        • L[idxA][idxB-1] 大,说明 A[maxLenIdxA] 可能与序列 B 中下一个字符相同,需要挪动序列 B:maxLenIdxB--;反之,则需要挪动序列 A:maxLenIdxA--
    • 具体的代码实现如下:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      string LCS;
      while(maxLenIdxA>=0 && maxLenIdxB>=0) {
      if(A[maxLenIdxA] == B[maxLenIdxB]) {
      LCS += A[maxLenIdxA];
      maxLenIdxA--;
      maxLenIdxB--;
      }
      else {
      if(maxLenIdxA == 0) {
      maxLenIdxB--;
      }
      else if(maxLenIdxB == 0) {
      maxLenIdxA--;
      }
      else {
      if(L[maxLenIdxA][maxLenIdxB-1] < L[maxLenIdxA-1][maxLenIdxB]) {
      maxLenIdxB--;
      }
      else {
      maxLenIdxA--;
      }
      }
      }
      }
文章目录
  1. 1. 最长公共子字符串
  2. 2. 最长公共子序列