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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        List<int[]> candidates = new ArrayList<>();

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > 0) {
                        int len = dp[i][j];
                        int sStart = i - len;
                        int tStart = j - len;
                        candidates.add(new int[] {len, sStart, tStart});
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        if (candidates.isEmpty()) {
            System.out.println("");
            return;
        }

        int maxLen = 0;
        for (int[] candidate : candidates) {
            if (candidate[0] > maxLen) {
                maxLen = candidate[0];
            }
        }

        List<int[]> maxCandidates = new ArrayList<>();
        for (int[] candidate : candidates) {
            if (candidate[0] == maxLen) {
                maxCandidates.add(candidate);
            }
        }

        String shortStr = (s.length() <= t.length()) ? s : t;
        int minStart = Integer.MAX_VALUE;
        String result = "";

        for (int[] candidate : maxCandidates) {
            int currentStart;
            if (shortStr.equals(s)) {
                currentStart = candidate[1];
            } else {
                currentStart = candidate[2];
            }

            if (currentStart < minStart) {
                minStart = currentStart;
                if (shortStr.equals(s)) {
                    result = s.substring(candidate[1], candidate[1] + candidate[0]);
                } else {
                    result = t.substring(candidate[2], candidate[2] + candidate[0]);
                }
            }
        }

        System.out.println(result);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取两个字符串 s 和 t。
2. 动态规划表初始化：创建一个二维数组 dp 来存储最长公共子串的长度。
3. 填充动态规划表：遍历两个字符串，当字符相等时更新 dp 的值，并记录所有可能的公共子串信息。
4. 收集候选子串：将每个公共子串的长度及其起始位置存入列表。
5. 确定最长子串：找到最长公共子串，并根据较短字符串中的起始位置选择最早出现的子串。
6. 输出结果：打印最长公共子串。