题解 | #查找两个字符串a,b中的最长公共子串#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        /**
        1.dp[i][j]  s1 中以i结尾  s2以j结尾的 最长公共子串长度
        2.递推公式
            如果 s1[i] == s2[j]
                那么 dp[i][j]=dp[i-1][j-1]+1;
            如果不等那么直接为0
        3.遍历顺序
            左上到右下
        4.初始化 
            设置数组多一行一列
        5.举例推导
         */
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s1=in.next();
            String s2=in.next();
            //使s1是短的那个
            if(s1.length()>s2.length()){
                String temp=s1;
                s1=s2;
                s2=temp;
            }
            int max=0;
            int idx=0;
            int[][] dp=new int[s1.length()+1][s2.length()+1];

            for(int i=0;i<s1.length();i++){
                for(int j=0;j<s2.length();j++){
                    if(s1.charAt(i)==s2.charAt(j)){
                        dp[i+1][j+1]=dp[i][j]+1;
                        if(dp[i+1][j+1]>max){
                            max=dp[i+1][j+1];
                            idx=i;
                        }
                    }
                }
            }

            System.out.println(s1.substring(idx-max+1,idx+1));

        }
    }
}