在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。

https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2

解法1 – 动态规划

Wiki中提到要寻找最长公共子串,可以在两个字符串中所有的前缀组合中寻找最长的公共后缀。

例如:S1=”ABAB”, S2=”BABA”。那么S1与S2的所有前缀组合有(A, B) (A, BA) (A, BAB), (A, BABA), …, (ABAB, BABA)。我们可以使用一个矩阵来描述所有前缀的组合,表头代表两个字符串,表中的数值代表两个前缀的最长后缀。表头中的双引号代表空串,因为空串是任何字符串的前缀。

“”ABAB
“”00000
B00101
A01020
B00203
A01030

我们很容易我们可以填好S1或S2只取一个字符后与另一个字符串的最长公共后缀,如果相同则填1,不同填0。那么如果S1或S2取两个字符与另一个字符串的最长公共后缀怎么求呢?我们可以看两个前缀最后一个字符,如果不相同那么该位置肯定是0,因为公共子串要求相同的字符连续。如果两个前缀最后一个字符相同,我们再对两个前缀各往回看一个字符,也就是该位置的斜上方。我们用斜上方的数值+1填入矩阵即可。

总结成公式也就是:

引自Wikipedia

下面我们编写代码,把这个矩阵填充出来。我们在实现中,我们不需为空串单独在矩阵中存储。我们发现s1或s2的长度为0时,直接返回空字符串即可。所以这个矩阵看起来应该是上面的矩阵去掉双引号的行和列。

String LCS(String s1, String s2) {
    /*
        在实现中,我们不需为空串单独在矩阵中存储。我们发现s1或s2的长度为0时,直接返回空字符串即可
        *------S2------
        |
        |
        |
        S1
        |
        |
        |
    */
    if (s1==null || s2 ==null || s1.length() == 0 || s2.length() == 0)
        return "";
    
    int[][] mtx = new int[s1.length()][s2.length()];
    int maxRid = 0, maxCid = 0;

    for (int rid = 0; rid < s1.length(); rid++) {
        for (int cid = 0; cid < s2.length(); cid++) {
            if(s1.charAt(rid) == s2.charAt(cid)) {
                // 填充第一行或第一列
                if (rid == 0 || cid == 0)
                    mtx[rid][cid] = 1;
                else // 否则该位置由左上角而来
                    mtx[rid][cid] = mtx[rid - 1][cid - 1] + 1;

                // 记录下最长公共子串的位置
                if (mtx[maxRid][maxCid] < mtx[rid][cid]) {
                    maxRid = rid;
                    maxCid = cid;
                }
            }
        }
    }

    return getLCS(mtx, maxRid, maxCid, s1, new StringBuilder());
}

下面,我们从填充好的矩阵mtx求得公共子串。通过观察上面形成的矩阵,我们发现从最大的非零元出发,“往斜上方走”就可以求得最长公共子串。往斜上方走这个操作明显带有递归性质,每走一次行号与列号均减一。因此我们可以编写函数,递归调用直到从矩阵里读到0或者行号或者列号越界。

String getLCS(int[][] mtx, int rid, int cid, String s1, StringBuilder builder) {
    if (rid < 0 || cid < 0 || mtx[rid][cid]==0) {
        return builder.reverse().toString();
    }
    builder.append(s1.charAt(rid));
    return getLCS(mtx, rid - 1, cid - 1, s1, builder);
}
pwrliang Algorithms, Dynamic Programming

Leave a Reply

Your email address will not be published. Required fields are marked *