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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String a = null;
        String b = null;
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String curLine = in.nextLine();
            if (a == null) {
                a = curLine;
                continue;
            }
            if (b == null) {
                b = curLine;
            }
        }

        System.out.println(commonLongSubStrUseDp(a, b));
    }

    private static String commonLongSubStrUseDp(String a, String b) {
        if (a == null || b == null) {
            return "";
        }
		// 此处交换位置，让a的字符串保持是最短的。
        if (a.length() > b.length()) {
            return commonLongSubStrUseDp(b, a);
        }

        if (a.contains(b)) {
            return b;
        }

        int m = a.length() + 1;
        int n = b.length() + 1;
        // 动态规划
        // dp[i][j]到a的第i个下标结尾，b的第j个下标结尾的是公共子串
        // 如果到字符串a下标i的位置，到字符串b的j位置是公共子串，那么，到第i-1个，以及第j-1个位置也是公共子串
        // 动态规划公式：dp[i][j] = dp[i-1][j-1]+1;

        int[][] dp = new int[m][n];
        int maxLen = 0;
        int index = 0;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        index = i;
                    }
                }
            }
        }
        return a.substring(index - maxLen, index);

    }
}