Java算法——求出两个字符串的最长公共字符串

浏览数：15 / 时间：2015年06月08日

问题：有两个字符串str1和str2，求出两个字符串中最长公共字符串。

例如：“acbbsdef”和"abbsced"的最长公共字符串是“bbs”

算法思路：

1、把两个字符串分别以行和列组成一个二维矩阵。

2、比较二维矩阵中行和列对应的每个点的字符是否相同，是设置这个点为1，否设置这个点为0。

3、通过查找值为1的最长对角线来找到最长公共字符串。

通过上面str1和str2两个字符串,分别得出以行和列组成的一个二维矩阵如下图：

从上图可以看到，str1和str2共有3个公共子串"bbs"，公共子串长度为3。

为了避免后续查找对角线长度的操作：

可以先计算二维矩阵值的时候顺便计算出来当前最长的公共子串的长度；

即：某个二维矩阵元素的值由item[i][j]=1演变为item[i][j]=1 +item[i-1][j-1]。

下面是代码实现

public class MaxStringDemo {

    public static void main(String[] args) {
        String aa = "abc123edf";
        String bb = "bc123jg";
        maxUtil2(aa, bb);
        System.out.println(maxUtil2(aa, bb));
    }

    public static StringBuilder maxUtil2(String str1, String str2) {
        //把字符串转成字符数组
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        // 把两个字符串分别以行和列组成一个二维矩阵
        int[][] temp = new int[arr1.length][arr2.length];
        // 存储最长公共子串长度
        int length = 0;
        //start表明最长公共子串的起始点，end表明最长公共子串的终止点
        int end = 0;
        int start = 0;
        ////初始化二维矩阵中的第一行
        for (int i = 0; i < arr2.length; i++) {
            temp[0][i] = (arr1[0] == arr2[i]) ? 1 : 0;
        }
        //初始化二维矩阵中的第一列
        for (int j = 0; j < arr1.length; j++) {
            temp[j][0] = (arr2[0] == arr1[j]) ? 1 : 0;
        }
        //嵌套for循环：比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0
        for (int i = 1; i < arr1.length; i++) {
            for (int j = 1; j < arr2.length; j++) {
                if (arr1[i] == arr2[j]) {
                    temp[i][j] = temp[i - 1][j - 1] + 1;

                    if (temp[i][j] > length) {
                        length = temp[i][j];
                        end = j;
                    }
                } else
                    temp[i][j] = 0;

            }
        }
        //求出最长公共子串的起始点
        start=end-length+1;
        StringBuilder sb=new StringBuilder();
        //通过查找出值为1的最长对角线就能找到最长公共子串
        for (int j = start; j < end+1; j++) {
            sb.append(arr2[j]);
        }

        return sb;
    }

}