题解 | #最长公共子串#

注意和最长子序列的区别：最长子序列要求序列可以不连续，子串要求必须连续，中间不能间隔其它字符串。因此，把状态方程改一下即可，dp[i][j]只能来自dp[i-1][j-1],并且用一个max记录当前最长的公共子串。至于最后截取字符串的时候为什么要加个1呢？那是因为公共子串若存在，那么最小值为1，在最后加个1可以免去定义dp数组进行初始化全体赋1的操作。

public class Solution {
    public String LCS (String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int dp[][] = new int [len1+1][len2+1];
        int max = 0;
        int end = 0;
        for(int i=1;i<=len1;++i){
            for(int j=1;j<=len2;++j){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(max<dp[i][j]) {
                        max = dp[i][j];
                        end = i-1;
                    }
                }
            }
        }
      String s= str1.substring(end-max+1,end+1);
      return s;
    }
}