查找两个字符串中的最长公共子串

思路：（动态规划）

用二维矩阵来储存两个字符串间字符是否相等的信息
直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

图片.png

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

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

图片.png

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

java实现

1. 重要的方法

• String类.charAt(index)，值为该字符串此位置的字符。
  示例：String a = "abc"; a.charAt(2)的值为c；
• String类.substring(start,end); 左必右开[start,end)，值为该字符串此段区域的字符串
  示例：String a = "abcde"; a.substring(1,4)的值为bcd；

public class MaxGonggongZIChuang {
    public static String maxSubstring(String a, String b) {
         //检查参数
        if(a == null || b == null) {
            return null;
        }
        
      //记录两个字符串的长度，创建二维数组
        int length1 = a.length();
        int length2 = b.length();
        int[][] arrs = new int[length1][length2];
    //用来记录最大公共子串的最后一个字符的位置
        int lastIndex = 0;
    //用来记录最大公共子串的长度
        int maxLength = 0;
        for(int i = 0; i < length1; i++) {
            for(int j = 0; j < length2; j++) {
                if(a.charAt(i) == b.charAt(j)) {
                       //当相等的位置在上边界和左边界时，没有左上角的数，记录的长度置1
                    if(i == 0 || j == 0) {
                        arrs[i][j] = 1;
                    }else {
                       //记录的长度等于左上角加1
                        arrs[i][j] = arrs[i - 1][j - 1] + 1;
                    }
                      //更新最长公共子串位置和长度信息
                    if(maxLength < arrs[i][j]) {
                        maxLength = arrs[i][j];
                        lastIndex = i;
                    }
                }
            }
        }
        //长度为0时，表示没有公共子串，返回null
        if(maxLength == 0) {
            return null;
        }
        return a.substring(lastIndex + 1 - maxLength, lastIndex + 1);
    }
    public static void main(String[] args) {
        String a = "123456789";
        String b = "123567894567";
        System.out.println(maxSubstring(a,b)); 
    }
}