题解 | #最长公共子串#

    //dp[i][j]表示str1 以第i个字符结尾，str2以第j个字符结尾的 最长子串的长度（i,j从1开始）

    public static String LCSolution2 (String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();

        int[][] dp = new int[len1+1][len2+1];

        int maxLen = 0;//记录最长长度
        int indexEnd = 0;//记录最后的索引位置

        //填写dp[][]
        for (int i = 1;i < len1+1;i++){
            for (int j = 1; j < len2+1; j++){
                if (str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    //判断更新maxlen 和 indexEnd
                    if (dp[i][j] > maxLen){
                        maxLen = dp[i][j];
                        indexEnd = j-1;
                    }
                }else {
                    dp[i][j] = 0;
                }
            }
        }
        return str2.substring(indexEnd-maxLen+1,indexEnd+1);
    }