首页 > 基础算法 > 字符串处理 > 最长公共子串-动态规划
2014
10-23

最长公共子串-动态规划

最长公共子序列 & 最长公共子串的区别:

找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。最长公共子序列的问题参考:最长公共子序列

这两个都可以使用动态规划解决,但是思路不太一样。

我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:”bab”和”caba”(当然我们现在一眼就可以看出来最长公共子串是”ba”或”ab”)

   b  a  b

c  0  0  0

a  0  1  0

b  1  0  1

a  0  1  0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。

   b  a  b

c  0  0  0

a  0  1  0

b  1  0  2

a  0  2  0

这样矩阵中的最大元素就是 最长公共子串的长度。

public class LongestSubString {

    public static String longestSubstring(String str1, String str2) {

        StringBuilder sb = new StringBuilder();
        if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
            return "";

        int[][] num = new int[str1.length()][str2.length()];
        int maxlen = 0; //记录最长字串的长度
        int lastSubsBegin = 0; //记录最长子串开始的位置

        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    if ((i == 0) || (j == 0))
                        num[i][j] = 1;
                    else
                        num[i][j] = 1 + num[i - 1][j - 1];

                    if (num[i][j] > maxlen) {
                        maxlen = num[i][j];
                        //当前最长的子串,在str1中开始的位置
                        int thisSubsBegin = i - num[i][j] + 1;

                        //如果是同一个子串
                        if (lastSubsBegin == thisSubsBegin) {
                            sb.append(str1.charAt(i));
                        } else {
                            //不是话的重新生成一个新的子串
                            lastSubsBegin = thisSubsBegin;
                            sb = new StringBuilder();
                            sb.append(str1.substring(lastSubsBegin, i + 1));
                        }
                    }
                }
            }}

        return sb.toString();
    }

    public static void main(String args[]){
        String str = longestSubstring("hello world","cpp hello java");
        System.out.println(str);
    }
}

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。

参考:http://my.oschina.net/leejun2005/blog/117167


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。