题解 | 公共子串计算

import java.util.*;
import java.lang.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String sb1 = in.nextLine();
            String sb2 = in.nextLine();
            String longSb,shortSb;
            if(sb1.length()<sb2.length()) {
                longSb = sb2;
                shortSb = sb1;
            }else{
                longSb = sb1;
                shortSb = sb2;
            }
            int maxLen = 0;
            int[][] dp = new int[shortSb.length()][longSb.length()];
            for(int i=0;i<shortSb.length();i++) dp[i][0] = shortSb.substring(i,i+1).equals(longSb.substring(0,1))? 1:0;
            for(int i=0;i<longSb.length();i++) dp[0][i] = longSb.substring(i,i+1).equals(shortSb.substring(0,1))? 1:0;
            for(int i=1;i<shortSb.length();i++){
                for(int j=1;j<longSb.length();j++){
                    dp[i][j] = shortSb.substring(i,i+1).equals(longSb.substring(j,j+1))? 1+dp[i-1][j-1]:0;
                }
            }
            for(int i=0;i<shortSb.length();i++)
                for(int j=0;j<longSb.length();j++)
                    maxLen = Math.max(maxLen,dp[i][j]);
            System.out.println(maxLen);
        }
    }
}

dp，设定dp[i][j]代表两个数组分别以i/j结尾，并且s1[i]==s2[j]的情况下的最长公共子串长度。

为什么要这么设计呢？ 因为：我们想要找到状态转移方程，那么必须得要尾巴可以续上的，比如axa和waxa，最长公共子串是axa，在第一个a的时候最长是1，在x的时候可以续上前面的a，在第二个a的时候又可以续上前面的x，这就构成了“可继承上一个计算结果”的特点，符合dp的特性