本文介绍如何在 Java 中高效找出 n 个输入字符串的最长公共子串（Longest Common Substring），要求该子串必须严格出现在所有字符串中，否则输出空字符串；代码兼顾正确性与可读性，并指出关键逻辑陷阱与优化建议。
本文介绍如何在 java 中高效找出 n 个输入字符串的**最长公共子串**（longest common substring），要求该子串必须**严格出现在所有字符串中**，否则输出空字符串；代码兼顾正确性与可读性，并指出关键逻辑陷阱与优化建议。
要解决“给定 n 个字符串，找出同时存在于所有字符串中的最长连续子串”这一问题，核心在于：以第一个字符串为基准，枚举其所有可能的子串，逐一验证是否在其余每个字符串中均存在。只有当某子串在全部 n 个字符串中都出现时，才具备候选资格；在所有合格子串中取长度最大者即为答案。
以下是一个结构清晰、逻辑严谨的 Java 实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // 使用 int 更安全（避免 byte 溢出）
input.nextLine(); // 消费换行符，防止 nextLine() 读取异常
String[] words = new String[n];
for (int i = 0; i < n; i++) {
words[i] = input.nextLine().trim(); // 安全读取并去除首尾空白
}
System.out.println(findLongestCommonSubstring(words));
}
public static String findLongestCommonSubstring(String[] words) {
if (words == null || words.length == 0) return "";
if (words.length == 1) return words[0]; // 边界情况：单字符串即自身
String base = words[0];
String longest = "";
// 枚举 base 的所有子串：从长到短遍历可提前终止（优化点）
// 这里采用常规从短到长 + 最终更新，更易理解；实际生产推荐“长度降序+首次命中即返回”
for (int i = 0; i < base.length(); i++) {
for (int j = i + 1; j <= base.length(); j++) {
String candidate = base.substring(i, j);
// 检查 candidate 是否存在于其余所有字符串中
boolean isCommon = true;
for (int k = 1; k < words.length; k++) {
if (!words[k].contains(candidate)) {
isCommon = false;
break;
}
}
// 更新最长有效子串
if (isCommon && candidate.length() > longest.length()) {
longest = candidate;
}
}
}
return longest;
}
}✅ 关键实现说明：
- 基准选择：以 words[0] 为枚举源，因其子串数量最少（减少冗余），且能覆盖所有可能解（公共子串必在任一字符串中出现）。
- 存在性检查：使用 String.contains() 替代手动循环截取比对，语义清晰、代码简洁、不易出错（原答案中嵌套 k 循环的边界条件 k
- 边界防护：添加 null/空数组校验、单字符串特例处理，并用 trim() 避免因输入空格导致误判。
- 输入健壮性：input.nextInt() 后调用 input.nextLine() 消费残留换行符，防止后续 nextLine() 读取为空。
⚠️ 注意事项与常见误区：
立即学习“Java免费学习笔记（深入）”；
- ❌ 不是“最长公共子序列（LCS）”：子串要求连续字符，而子序列允许不连续，二者算法完全不同。
- ❌ 不是“公共前缀”：如 "abc" 和 "abx" 公共前缀为 "ab"，但公共子串还包括 "a"、"b"、"c"（若存在）、"ab" 等，需穷举所有位置。
- ⚠️ 时间复杂度为 O(L³ × n)（L 为平均字符串长度），适用于小规模输入（n ≤ 10，L ≤ 100）。若需处理大规模数据，应改用后缀数组或广义后缀自动机（SAM）等高级算法。
- ? 输出为空字符串 "" 表示无任何非空公共子串（包括长度为 1 的字符），符合题目“一个缺失即不输出”的要求。
? 总结：本方案以清晰逻辑优先，在保证正确性的前提下提升可维护性。掌握此基础实现后，可进一步探索基于滚动哈希（Rabin-Karp）的优化版本，或封装为通用工具方法（如支持自定义比较器、忽略大小写等），以适配更复杂的业务场景。
