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

经典的动态规划题目，注意满足题目条件即可。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { 
            String s11 = in.nextLine();
            String s22 = in.nextLine();
            String s1 = s11.length()<s22.length()?new String(s11):new String(s22);
            String s2 = s11.length()<s22.length()?new String(s22):new String(s11);
            String res="";
            int max = 0;
            int [][] dp = new int[s1.length()+1][s2.length()+1];
            for(int i=1;i<=s1.length();++i){
                for(int j=1;j<=s2.length();++j){
                    if(s1.charAt(i-1)==s2.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }
                    if(dp[i][j]>max){
                        max  = dp[i][j];
                        res = s1.substring(i-max,i);
                    }
                }
            }
            System.out.println(res);
        }
    }
}