动态规划解最长公共子序列及最长公共字串问题

【问题】 求两字符序列的最长公共字符子序列

问题描述:

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:

(1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;

(2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;

(3) 如果am-1!=bn-1,则若zk-1!=bn-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。

这样,在找A和B的公共子序列时,如有am-1=bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列

求解:

引进一个二维数组c[][],用c[i][j]记录X[i]与Y[j] 的LCS 的长度,b[i][j]记录c[i][j]是通过哪一个子问题的值求得的,以决定搜索的方向。
我们是自底向上进行递推计算,那么在计算c[i,j]之前,c[i-1][j-1],c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j],就可以计算出c[i][j]。

问题的递归式写成:

回溯输出最长公共子序列过程:

即,从上到下,从左到右,如果c[i][j]所对应的字符相等,则c[i][j]=c[i-1][j-1]+1,否则c[i][j]等于其左边或上边较大的数字。

其编程实现

public void LCS(String a, String b) {
    char[] sa = a.toCharArray(), sb = b.toCharArray();
    int[][] dp = new int[sa.length + 1][sb.length + 1];
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (sa[i - 1] == sb[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    System.out.println("Length of LCS is:" + dp[dp.length - 1][dp[0].length - 1]);
    
    StringBuilder result = new StringBuilder();
    int i = sa.length - 1, j = sb.length - 1;
    while (i >= 0 && j >= 0) {
        if (sa[i] == sb[j]) {
            result.append(sa[i]);
            i--;
            j--;
        } else if (dp[i + 1][j] > dp[i][j + 1])
            j--;
        else
            i--;
    }
    System.out.println(result.reverse().toString());
}

最长公共字串

比子序列简单,就不写方法了。

public void LCS(String a, String b) {
    char[] sa = a.toCharArray(), sb = b.toCharArray();
    int[][] dp = new int[sa.length + 1][sb.length + 1];
    int max=0;
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (sa[i - 1] == sb[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max=Math.max(max,dp[i][j]);
            }

        }
    }

    System.out.println("Length of LCS is:" + max);

    for(int i=0;i<sa.length;i++){
        for(int j=0;j<sb.length;j++){
            if(dp[i+1][j+1]==max){
                System.out.println(a.substring(i-max+1,i+1));
                break;
            }
        }
    }
}