链接：https://www.nowcoder.com/questionTerminal/98dc82c094e043ccb7e0570e5342dd1b
来源：牛客网
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1≤s≤150
进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)
解题思路：
对于动态规划来说，我们没办法一下子解决这个大问题，需要划分成小问题，我们先看每个字符串的子串之间最大公共子串的长度，然后用小问题的解推倒大问题
我们定义一个函数：
F（i,j）表示以第一个字符串第i个字符结尾和第二个字符串第j个字符结尾的最大公共子串的长度
举个例子：
F（1,1）表示：第一个字符串的以第1个字符a结尾的子串，第二个字符串的以第1个字符w结尾的子串，最大公共子串长度为0
同理得：
F（2,3）: … s,… r，最大公共子串长度为0
F（4,7）: …f,… f，最大公共子串长度肯定大于等于1了（f是相同的,f前面的也有可能相同）
推广开来：
如果第i个字符!=第j个字符
F（i,j）=0
第i个字符==第j个字符
F(i,j)=F(i-1,j-1)+1
比如F(1,4)=1 字符串a
F(2,5)=F(1,4)+1=2 字符串as
F(3,6)=F(2,5)+1=3 字符串asd
初始状态：F（i,0）=F(0,j)=0
（你拿一个字符串和一个空串比，它们的子串肯定是0）
返回值：max(F(i,j))
代码如下：
import java.util.*;
public class Main{
public static int getMaxLen(String str1,String str2){
char[] arr1=str1.toCharArray();
char[] arr2=str2.toCharArray();
int l1=arr1.length;
int l2=arr2.length;
int[][] maxSubLen=new int[l1+1][l2+1];
int maxLen=0;
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(arr1[i-1]==arr2[j-1]){
//F(i,j)=F(i-1,j-1)+1
maxSubLen[i][j]=maxSubLen[i-1][j-1]+1;
//是否需要更新最大值
if(maxLen<maxSubLen[i][j]){
maxLen=maxSubLen[i][j];
}
}//如果不等，你就不用管了，原先数组里面默认就是0
}
}
return maxLen;
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String str1=scanner.nextLine();
String str2=scanner.nextLine();
int x=getMaxLen(str1,str2);
System.out.println(x);
}
}
