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

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine();
        String b = br.readLine();
        //交换位置，使a为短字符串
        if (a.length() > b.length()) {
            String temp = b;
            b = a;
            a = temp;
        }
        // dp[i]:a[i]开始的最长子串长度
        int max=0;
        int maxIndex = 0;
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    int k = 1;
                    while (i + k < a.length() && j + k < b.length() &&
                            a.charAt(i + k) == b.charAt(j + k)) {
                        k++;
                    }
                    if (k > max) {
                        maxIndex = i;
                        max = k;
                    }
                }
            }
        }
        System.out.print(a.substring(maxIndex, maxIndex + max));
    }
}