题解 | #最长公共子串#

请参考 该题为不连续的求解，所以状态方程的定义为前i-1个数，与此题不同，此题为连续子串

请参考 ，

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS(String str1, String str2) {
        // write code here
//        dp[i][j]表示以str1[i-1]和str2[j-1]为结尾的字符串的最长子序列
//         因为子串定义必须是原字符串连续的序列
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int maxlen = 0;
        int endstr2 = 0;
        for (int i = 1; i < str1.length() + 1; i++) {
            for (int j = 1; j < str2.length() + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {//如果结尾相同，就+1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {//如果不同就为0
                    dp[i][j] = 0;
                }
                if (dp[i][j] > maxlen) {//记录下最长额长度以及在str2上的结束下标
                    maxlen = dp[i][j];
                    endstr2 = j;
                }
            }

        }
        if (maxlen == 0) {
            return "-1";
        } else {
            return str2.substring(endstr2 - maxlen, endstr2);
        }

    }
}