题解 | #最长公共子串#

public String LCS(String str1, String str2) {
    int m = str1.length(), n = str2.length();
    if (m == 0 || n == 0) return "";
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < m + 1; i++) dp[i][0] = 0;
    for (int i = 0; i < n + 1; i++) dp[0][i] = 0;
    int maxLen = 0, index = 0;
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if(str1.charAt(i - 1) == str2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = 0;
            }
            // 记录长度，方便后面裁剪
            if(maxLen < dp[i][j]){
                maxLen = dp[i][j];
                index = j;
            }
        }
    }
    if(maxLen == 0) return "";
    return str2.substring(index - maxLen, index);
}