公共子串计算（牛客）

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

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


思路
可以用动态规划来写

状态
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 Scanner(System.in);
        String a = scan.nextLine();
        String b = scan.nextLine();
        int ret = commonLength(a,b);
        System.out.println(ret);
    }
    public static int commonLength(String s1, String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        int max = 0;
        //初始化f[i][j]
        int[][] f = new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                f[i][j] = 0;
            }
        }
        //若是s1[i] == s2[j]，F[i,j] = F[i-1,j-1] + 1
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    f[i][j] = f[i-1][j-1] + 1;
                }
                else f[i][j] = 0;
            }
        }
		//求最大值
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                if(f[i][j] > max){
                    max = f[i][j];
                }
            }
        }
        return max;
    }
}