思路：（動態(tài)規(guī)劃）

用二維矩陣來儲存兩個字符串間字符是否相等的信息
直接舉個例子吧："bab"和"caba"(當然我們現(xiàn)在一眼就可以看出來最長公共子串是"ba"或"ab")

圖片.png

我們看矩陣的斜對角線最長的那個就能找出最長公共子串。

不過在二維矩陣上找最長的由1組成的斜對角線也是件麻煩費時的事，下面改進：當要在矩陣是填1時讓它等于其左上角元素加1。

圖片.png

這樣矩陣中的最大元素就是 最長公共子串的長度。

java實現(xiàn)

1. 重要的方法

• String類.charAt(index)，值為該字符串此位置的字符。
  示例：String a = "abc"; a.charAt(2)的值為c；
• String類.substring(start,end); 左必右開[start,end)，值為該字符串此段區(qū)域的字符串
  示例：String a = "abcde"; a.substring(1,4)的值為bcd；

public class MaxGonggongZIChuang {
    public static String maxSubstring(String a, String b) {
         //檢查參數(shù)
        if(a == null || b == null) {
            return null;
        }
        
      //記錄兩個字符串的長度，創(chuàng)建二維數(shù)組
        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)) {
                       //當相等的位置在上邊界和左邊界時，沒有左上角的數(shù)，記錄的長度置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)); 
    }
}