暴力法时间复杂度O(n⁴)，不适用于长字符串；实用解法为后缀数组（SA）或后缀自动机（SAM），推荐用string_view+排序的简易SA变体，结合LCP求最长重复子串。
暴力法能解，但别真用在长字符串上
对长度为 n 的字符串，暴力枚举所有子串再两两比对，时间复杂度是 O(n⁴)（枚举起点、终点、另一起点、另一终点），哪怕加点剪枝也扛不住 n > 1000。实际遇到的文本（比如日志、DNA序列）动辄几万字符，必须换思路。
真正实用的解法只有两个方向：后缀数组（SA）或后缀自动机（SAM）。前者实现稍重但稳定；后者更省内存、支持在线，但调试门槛高。日常开发中，优先考虑基于 std::string_view + 排序的简易后缀数组变体，它能在 O(n² log n) 内跑通几千字符的场景。
用后缀数组+高度数组（LCP）找最长重复子串
核心思想：所有重复子串必然出现在至少两个不同后缀的公共前缀里；而最长重复子串，就是所有相邻后缀的最长公共前缀（LCP）中的最大值。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 构建所有后缀：
vector<string_view></string_view>存每个s.substr(i)，注意用string_view避免拷贝 - 排序后缀：
sort(suffixes.begin(), suffixes.end())，复杂度O(n² log n)（比较本身是O(n)） - 遍历相邻后缀，调用
common_prefix_length(a, b)计算 LCP —— 手写一个简单循环即可，别用std::mismatch（它返回迭代器，还得算距离） - 记录最大 LCP 长度和对应起始位置：
max_len和best_start = suffixes[i].data() - s.data()
示例片段：
int lcp(const string_view& a, const string_view& b) {
int n = min(a.size(), b.size());
for (int i = 0; i < n; ++i)
if (a[i] != b[i]) return i;
return n;
}遇到“ababa”这种重叠重复时，LCP 方法仍有效
有人担心 “ababa” 中 “aba” 出现两次且重叠，LCP 是否漏判？不会。后缀数组包含 "ababa"、"baba"、"aba"、"ba"、"a"，排序后 "a" 和 "aba" 相邻，LCP 是 1；"aba" 和 "ababa" 相邻，LCP 是 3 —— 正好捕获 “aba”。
关键点：
- LCP 只关心字符匹配长度，不管子串是否重叠
- 重复子串只要出现 ≥2 次，就必有至少一对后缀以它为公共前缀
- 重叠不影响正确性，但会影响你后续提取结果时的边界判断 —— 返回的是最长长度和起始下标，不是所有出现位置
别忽略边界情况和性能陷阱
空串、单字符、全相同字符（如 "aaaa"）这些 case 容易让 LCP 循环越界或漏处理。实操时务必检查：
- 输入
s.empty()→ 直接返回空string_view - 后缀数组大小为 1 时，跳过 LCP 计算
- 用
string_view时确保原字符串生命周期长于后缀容器 —— 别把临时std::string传进去再析构 - 若字符串超 5000 字符，
O(n² log n)会明显卡顿，此时必须上 SA-IS 或 SAM 实现，不能硬撑
最常被忽略的一点：最长重复子串可能有多个（如 “abcabc” 和 “defdef” 并存），LCP 方法只返回第一个最大值，如需全部，得遍历完所有 LCP 并收集等长结果。
