每日一题系列：公共子串计算

链接：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);
    }
}