题目：

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

示例1

输入：

"1AB2345CD","12345EF"

返回值：

"2345"

备注：

1≤∣str1∣,∣str2∣≤5 0001 \leq |str_1|, |str_2| \leq 5\,0001≤∣str1​∣,∣str2​∣≤5000

 思路：动态规划问题。

先确定状态，f(i, j)表示str1中前i个字符和str2中前j个字符中的最长公共子序列的长度

但这样写不出状态转移方程，因为这里 求解公共连续字符串 是没法形成递推关系的，因此增加限制条件：

f(i, j)表示str1中前i个字符和str2中前j个字符中的最长公共子序列的长度，且以第i个字符和第j个字符为结尾

可以简单写出状态转移方程

str1[i] == str2[j] 时，f[i][j] = f[i-1][j-1] + 1

str1[i] != str2[j] 时，f[i][j] = 0

但还有个问题，这个动态规划不能直接得到答案，需要用变量maxLength保存最长的长度

边界条件为：

i = 0 或 j = 0 时， f[i][j] = 0  

引自link

这里有张图：

 代码：

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
        String res = "";
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int l1 = str1.length();
        int l2 = str2.length();
        int[][] ans = new int[l1+1][l2+1];
        int last1 = 0;
        int max = 0;
        for(int i = 1; i<=l1;i++){
            for(int j=1;j<=l2;j++){
                if(s1[i-1] == s2[j-1])
                    ans[i][j] = ans[i-1][j-1] + 1;
                else
                    ans[i][j] = 0;
                if(ans[i][j]>max){
                    max = ans[i][j];
                    last1 = i;
                }
            }
        }
        for(int i=last1-max;i<last1;i++){
            res = res + s1[i];
        }
        return res;
    }
}