最长公共子序列

算法笔记
动态规划, 算法

问题描述
对于母串X={x1,x2,⋯,xm}, Y={y1,y2,⋯,yn}, 求LCS与最长公共子串。
假设 Zk={z1,z2,⋯,zk} 是 X 与 Y 的 LCS， 可以观察到

  • 如果xm=yn，则 zk=xm=yn，有 Zk−1 是 Xm−1、Yn-1 的 LCS；
  • 如果xm≠yn ，则 Zk 是 Xm 与 Yn−1 的LCS，或者 Xm−1 与 Yn 的 LCS

利用动态规划思想，不难写出状态转移方程：

1
2
if X[i]=Y[j]  then LCS(i,j) = LCS(i-1j-1)+1
              else LCS(i,j) = max(LCS(i-1,j) , LCS(i,j-1))

也就很容易有代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public static int lcs(String X, String Y) {
    int lx = X.length();
    int ly = Y.length();
    int[][] r = new int[lx+1][ly+1];
    for (int i = 0; i <= lx; i++) {
        for( int j = 0; j <= ly; j++) {
            if(i == 0 || j == 0) {
                r[i][j] = 0;
            } else if (X.charAt(i-1) == Y.charAt(j-1)) {
                r[i][j] = r[i-1][j-1] + 1;
            } else {
                r[i][j] = max(r[i - 1][j], r[i][j - 1]);
            }
        }
    }
    return c[lx][ly];
}

实际上这样带来的空间消耗还是比较大，观察到每次实际只用到了上一行保存的数字（不考虑复原LCS，只考虑计算其长度），可以将m*n的数组转为2*n的数组。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int lcs(String X, String Y) {
    int lx = X.length();
    int ly = Y.length();
    int[][] r = new int[2][ly+1];
    r[0][0]=0;
    int k =0;
    for (int i = 0; i <= lx; i++) {
        k = 1-k;
        for( int j = 1; j <= ly; j++) {
            if(i == 0) {
                r[i][j] = 0;
            } else if (X.charAt(i-1) == Y.charAt(j-1)) {
                r[k][j] = r[1-k][j-1] + 1;
            } else {
                r[k][j] = Math.max(r[1-k][j], r[k][j - 1]);
            }
        }
    }
    return r[k][ly];
}

求最长公共子串与上面类似，转移方程为：

1
2
if X[i]=Y[j]  then LCS(i,j) = LCS(i-1j-1)+1
     else LCS(i,j) = 0

分享到