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

import java.util.*;

/**
 * 查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String a = in.nextLine();
            String b = in.nextLine();
            Map<String, Integer> map = new HashMap<>();
            if (a.length() > b.length()) {
                getMaxChild(a, b, map);
            } else {
                getMaxChild(b, a, map);
            }
        }
    }

    /**
     * 求最长公共子串
     */
    private static void getMaxChild(String a, String b, Map<String, Integer> map) {
        // 先遍历较长的字符串，获取所有子串
        for (int i = 0; i < a.length(); i++) {
            for (int j = i + 1; j <= a.length(); j++) {
                map.put(a.substring(i, j), j - i);
            }
        }
        // 再遍历较短的字符串，找到最长的那个子串
        String maxStr = "";
        Integer maxLength = 0;
        for (int i = 0; i < b.length(); i++) {
            for (int j = i + 1; j < b.length(); j++) {
                String key = b.substring(i, j);
                // 此处条件要大于，不能等于，可以保证最后求出的是第一个出现的最长子串
                if (map.containsKey(key) && map.get(key) > maxLength) {
                    maxLength = map.get(key);
                    maxStr = key;
                }
            }
        }
        System.out.println(maxStr);
    }

}