PSJay Blog

#FIXME, seriously

最长公共子序列(LCS, Longest Common Subsequence)

| Comments

定义

假设有 A,B 两个字符串,A = “ABCDE", B = "ABDFE",那么 A 和 B 的最长公共子序列就是 Z =  "ABDE"。因为是子序列而不是子串,所以不要求构成子序列的字符在原串中是连续的。

为了方便讨论,设 S 为一个字符串 <s[1], s[2], … s[n]>。S 串的长度为 n。s[x] 表示 S 串的第 x 个字符,而 S[x] 表示 S 串的前 x 个字符组成的串,例如 S[2] = <s[1], s[2]>,特别的,S[0] 为空串。

子序列的严谨的定义为:设 A = <a[1], a[2], a[3], … a[m]>, B = <z[1], z[2], … z[n]> 中的每个字符都在 A 中,且在 A 中的下标都是严格递增时, B 就是 A 的子序列。

而最长公共子序列,就是指在多个串中,共有的,长度最长的子序列。最长公共子序列可能不存在,也可能存在多个。本篇文章讨论两个串的最长公共子序列。

一些性质

设 X = <x[1], x[2], … , x[m]>,Y = <y[1], y[2], …, y[n]>,Z = <z[1], z[2], …, z[k]>。Z 是 X 和 Y 的一个最长公共子序列。对 X, Y 和 Z 来说有如下性质:

  1. 若 x[m] = y[n],则 z[k] = x[m] = y[n],并且 Z[k-1] 也是 X[m-1] 和 Y[n-1] 的一个最长公共子序列。

  2. 若 x[m] != y[n],z[k] != x[m],则 Z 是 X[m-1] 和 Y 的一个最长公共子序列。

  3. 若 x[m] != y[n],z[k] != y[n],则 Z 是 X 和 Y[n-1] 的一个最长公共子序列。

这三点性质也很容易证明:

  1. 若 x[m] = y[n],根据定义, x[m] 和 y[n] 必定是 z[k]。

  2. 若 x[m] != y[n],z[k] != x[m],则 x[m] 不在 Z 中,Z 是 X[m-1] 和 Y 的一个最长公共子序列。

  3. 同上可证。

用 c[i, j] 表示 X[i] 和 Y[j] 的最长公共子序列长度。显然,c[0, j] 和 c[i, 0] 的值为 0。根据上面三条性质可以得到:

  1. 当 i, j > 0 且 x[i] = y[j] 时, c[i, j] = c[i -1, j -1] + 1。

  2. 当 i, j > 0 且 x[i] != y[j] 时,c[i, j] 等于 c[i-1, j] 和 c[i, j-1] 中的较大者。

因此,可以根据这个结论来解这个求 LCS 的长度问题。一个 Java 实现如下:

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
public class LCS {

  public static void main(String[] args) {
      String a = "ABCDE";
      String b = "ABDFE";

      System.out.println(getLcsLength(a, b));

  }

      public static int getLcsLength(String str1, String str2) {
      
      int str1Length = str1.length();
      int str2Length = str2.length();
      
      int lcsLen = 0;
      
      int[][] c = new int[str1Length + 1][str2Length + 1];
      
      for(int i = 0; i <= str1Length; i++) {
          c[i][0] = 0;
      }
      
      for(int i = 0; i <= str2Length; i++) {
          c[0][i] = 0;
      }
      
      for(int i = 1; i <= str1Length; i++) {
          for(int j = 1; j <= str2Length;j ++) {
              if(str1.charAt(i - 1) == str2.charAt(j - 1)) { //x[i] == j[j]
                  c[i][j] = c[i - 1][j - 1] + 1;
                  if(c[i][j] > lcsLen) {
                      lcsLen = c[i][j];
                  }
              } else {
                  if(c[i - 1][j] > c[i][j - 1]) {
                      c[i][j] = c[i - 1][j];
                  } else {
                      c[i][j] = c[i][j - 1];
                  }
              }
          }
      }
      
      return lcsLen;
  }

}

Comments