最长公共子串可用后缀数组+LCP或后缀自动机（SAM）在线性/近线性时间内求解：前者拼接两串后构建SA与height数组，扫描height过滤跨串位置取最大值；后者以str1建SAM、用str2匹配并动态更新最长长度，时间空间更优。
对两个大文本字符串做最长公共子串查找，不能用暴力枚举或二维 DP 表——前者时间爆炸，后者空间超限（比如各 10MB 文本，DP 表需约 100TB 内存）。高效方案必须绕开 O(n×m) 空间与 O(n²m) 时间陷阱，核心思路是：**用后缀数组 + 高度数组（LCP），或后缀自动机（SAM）在线性/近线性时间内完成**。
用后缀数组（SA）+ LCP 数组实现
这是最常用、原理清晰、工程落地性强的方法：
-
拼接预处理：将两文本用唯一分隔符连接，如
str1 + '\0' + str2（确保 '\0' 不在任一原文中）；长度记为n - 构建后缀数组 SA 和高度数组 height：SA[i] 表示字典序第 i 小的后缀起始位置；height[i] 表示 SA[i] 与 SA[i−1] 对应后缀的最长公共前缀长度
-
扫描 height 数组过滤跨串匹配：对每个 i ≥ 1，检查 SA[i] 和 SA[i−1] 是否分别落在 str1 和 str2 的索引范围内（即一个
len(str1)，另一个 >len(str1)）；满足则height[i]是一个合法公共子串长度 -
取最大值并还原子串：记录所有满足条件的 height[i] 的最大值
maxLen及其对应位置，从原拼接串中截取s[SA[i]]开始的maxLen个字符即可
Java 中可用 现成 SA 构建库（如 DC3 或 SA-IS 实现），避免手写 O(n log²n) 排序。实际运行时间通常在 O(n log n)，内存占用约 O(n)。
用后缀自动机（SAM）实现
适合单次查询、内存更敏感的场景，理论最优 O(n + m) 时间与空间：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
立即学习“Java免费学习笔记（深入）”；
-
以 str1 构建 SAM：每个状态记录
len（该状态能表示的最长子串长度）和link（后缀链接） -
用 str2 在 SAM 上匹配：维护当前匹配长度
curlen和当前状态cur；逐字符遍历 str2，若转移存在则curlen++、cur = cur.next[c]；否则沿link回跳并缩短curlen，直到转移存在或cur = root -
动态更新全局最大值：每步匹配后，用
curlen更新答案；最终得到的就是最长公共子串长度；要获取子串内容，可在匹配过程中记录结束位置和长度，反推起始点
SAM 实现稍复杂，但无排序开销，对超长文本（如百 MB 级）更稳定。已有成熟 Java 实现（如 indy256/cf-java 中的 SAM 类）可直接集成。
实用建议与避坑点
真实场景下，别从零造轮子：
- 中小规模（≤ 10⁵ 字符）：直接用优化版二维 DP（滚动数组压缩空间至 O(min(m,n))），代码简短、调试快
-
大文本但内存充足：优先选 SA + LCP，配合
Arrays.sort()+ 自定义比较器做简易后缀排序（O(n² log n) 可接受，且易 debug） -
分隔符必须真正唯一：不要用空格、逗号等常见字符；推荐用 Unicode 辅助字符如
'\uFFFD'或自定义 byte 值（若用 byte[] 处理） -
注意边界情况：空串、一方为空、无公共子串时返回空字符串而非 null；Unicode 多码点字符（如 emoji）需用
codePointCount和offsetByCodePoints安全切片
不复杂但容易忽略。
