题解 | 最长公共子串

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 s, String t) {
        // write code here

        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m + 1][n + 1]; // 以 s[i-1] t[j-1]为终点的 最长公共子串长度
        int max = 0;
        int maxEnd = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    maxEnd = i; // 记录终点 此处 i 是指个数 不是索引 所以 后续计算子串不需要加 1
                }
            }
        }
        return s.substring(maxEnd - max, maxEnd);
    }
}