公共子串计算（牛客）

题目
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。

注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。


思路
可以用动态规划来写

状态
F[i,j]：字符串s1的前i+1个字符与字符串s2的前j+1个字符中以s1[i]和s2[j]为结尾的最长公共子串的长度。即所求得的公共子串必须是以s1[i]和s2[j]为结尾的。

例如：s1：wtabcwedht；s2：zabcyedff
那么F[3,2]则代表的是s1的前4(因为字符串下标以0开始)个字符组成的字符串"wtab"与s2的前3个字符组成的字符串"zab"以s1[3]即b和s2[2]即b为结尾的最长公共子串"ab"，对应的长度则为2；
F[5,3]对应的长度则为0；s1的前6个字符组成的字符串"wtabcw"与s2的前4个字符组成的字符串"zabc"的最长公共子串为"abc"，但是"abc"并没有以w结尾，所以它不是有效的。

通过这种状态设置方法，现在我们只需判断s1[i]与s2[j]是否相等即可判断下一个状态的变化。
状态转移方程
若是s1[i] == s2[j]，F[i,j] = F[i-1,j-1] + 1
若是s1[i] != s2[j]，F[i,j] = 0

初始状态
F[i][j] = 0

返回
max(F[i][j])
因为此时F[i][j]矩阵中存储的公共子串的长度只是局部最优的结果，例"abc"和"abctttbc"中F[2][7]的值为2（“bc”)，但实际上它的最大公共子串长度应为3（F[2][2]所对应的值)。
所以实际返回值应为F[i][j]矩阵中的最大值。

代码

import java.util.Scanner;

public class Main{
   
    public static void main(String[] args){
   
        Scanner scan = new 
1
2
3
4
5
6