注意：要和最长公共子列的问题比较来学
    二者的关键区别在于dp[i][j]的含义不同，从而导致初始化时不同
    本题中
    dp[i][j]表示的是，在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下，公共子串最长能有多长。
    而最长公共子列中
    dp[i][j]表示的是str1[0…i]与str2[0…j]的最长公共子序列的长度
    这种区别也导致了在回溯寻找最长公共子序列和最长公共子串时的区别。

    1. public int[][] getdp(char[] str1, char[] str2){
    2.     int[][] dp = new int[str1.length][str2.length];
    3.     for(int i = 0; i < str1.length; i++){
    4.         if(str1[i] == str2[0]) {
    5.             dp[i][0] = 1;
    6.         }
    7.     }
    8.     for(int j = 1; j < str2.length; j++){
    9.         if(str1[0] == str2[j]){
    10.             dp[0][j] = 1;
    11.         }
    12.     }
    13.     for(int i = 1; i < str1.length; i++) {
    14.         for(int j = 1; j < str2.length; j++) {
    15.             if(str1[i] == str2[j]) {
    16.                 dp[i][j] = dp[i - 1][j - 1] + 1;
    17.             }else{
    18.                 //这句是多余的，只是为了展示思路，和最长公共子序列进行比较
    19.                 dp[i][j] = 0;
    20.             }
    22.         }
    23.     }
    24.     return dp;
    25. }
    27. public String lcst1(String str1, String str2) {
    28.     if(str1 == null || str2 == null || str1.equals("") || str2.equals("")){
    29.         return "";
    30.     }
    31.     char[] chs1 = str1.toCharArray();
    32.     char[] chs2 = str2.toCharArrAy();
    33.     int[][] dp = getdp(chs1, chs2);
    34.     int end = 0;
    35.     int max = 0;
    36.     for(int i = 0; i < chs1.length; i++){
    37.         for(int j = 0; j < chs2.length; j++){
    38.             if(dp[i][j] > max) {
    39.                 end = i;
    40.                 max = dp[i][j];
    41.             }
    42.         }
    43.     }
    44.     return str1.substring(end - max + 1, end + 1);
    45. }