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

使用动态规划进行解决

dp[i][j]表示以str1[i]和str2[j]结尾的公共子串的长度，因此可以得到递推式

dp[i][j] = dp[i-1][j-1] + (1 & str1[i]==str2[j])

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            String longest =  longestCommonSubstring(str1,str2);
            System.out.println(longest);
        }
    }
    
    public static String longestCommonSubstring(String str1, String str2){
        if(str1.length() == 0 || str2.length() == 0){
            return "";
        }
        // 保证str1的长度<=str2
        if(str1.length() > str2.length()){
            return longestCommonSubstring(str2, str1);
        }
        int m = str1.length(), n = str2.length();
        //使用dp[i][j]表示以i,j结尾的最长公共子串长度
        //dp[i][j] = dp[i-1][j-1] + 1;
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            if(str1.charAt(i) == str2.charAt(0)){
                dp[i][0] = 1;
            }
        }
        for(int i = 0; i < n; i++){
            if(str1.charAt(0) == str2.charAt(i)){
                dp[0][i] = 1;
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
            }
        }
        int maxLen = 0;
        int end = 0; //从str1上取的end，也就是表示优先取str1上第一次出现的
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dp[i][j] > maxLen){
                    maxLen = dp[i][j];
                    end = i;
                }
            }
        }
        return str1.substring(end-maxLen+1 ,end+1);
        
    }
    
}