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

使用dp方法求解

dp方程的含义的是第一个串的位置i到第二个串的位置j之间，最长公共子串长度

注意跟子序列的区别。

时间复杂度O(m*n)

空间复杂度O(m*n)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String l1 = in.nextLine();
        if(s1.length()>l1.length()){
            String temp = s1;
            s1=l1;
            l1=temp;
        }
        int max=0;
        int index=0;
        int[][] dp = new int[s1.length()+1][l1.length()+1];
        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=l1.length();j++){
                if(s1.charAt(i-1)==l1.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                        if(dp[i][j]>max){
                    max=dp[i][j];
                    index=i-1;

                }
                }
            

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