公共子串計算（牛客）

題目

給定兩個隻包含小寫字母的字元串，計算兩個字元串的最大公共子串的長度。

注：子串的定義指一個字元串删掉其部分字首和字尾（也可以不删）後形成的字元串。

思路

可以用動态規劃來寫

狀态

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;
    }
}