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

java dp

import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextLine()) {
                String a = sc.nextLine();
                String b = sc.nextLine();
                String longStr = (a.length() > b.length())? a:b;
                String shortStr = (a.length() < b.length())? a:b;
                int[][] dp = new int[shortStr.length()+1][longStr.length()+1];
                int res = 0;
                int index = 0;
                for (int i = 1; i <= shortStr.length(); i++ ) {
                    for (int j = 1; j <= longStr.length(); j++) {
                        if (shortStr.charAt(i-1) == longStr.charAt(j - 1)) {
                            dp[i][j] = dp[i-1][j-1] +1;
                            if (dp[i][j] > res) {
                                res = dp[i][j];
                                index = i;
                            }
                        } 
                    }
                    
                }
                
                if (res > 0) {
                    System.out.println(shortStr.substring(index - res,index));
                }
            }
        }
}