后缀数组用数组实现的核心是提取所有后缀、字典序排序并记录起始位置；拼接两文本加唯一分隔符后构建sa，再通过height数组或相邻后缀lcp验证可高效求最长公共子串。
用数组实现后缀数组，核心是把字符串所有后缀提取出来、按字典序排序、再记录每个排好序的后缀在原串中的起始位置。这个结构一旦建好，找两个文本变量的最长公共子串就变得高效且清晰。
用普通数组构建后缀数组
不需要复杂算法也能上手：遍历原字符串每个下标 i，截取子串 s[i:]，同时保存起始位置 i；把所有（后缀字符串，起始索引）组成列表，按字符串本身排序；最后只取出索引列，就是后缀数组 SA。
- Python 示例（简洁可读）：
def suffix_array(s):
if not s: return []
suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])
return [idx for _, idx in suffixes]
- 对 "banana" 调用返回 [5, 3, 1, 0, 4, 2]，对应后缀 "a", "ana", "anana", "banana", "na", "nana"
- 时间复杂度约 O(n² log n)（因字符串比较耗时），适合理解原理和中小规模数据
拼接+标记法处理多文本变量
要查两个变量 str1 和 str2 的最长公共子串，不能直接分别建数组——必须让它们“可区分又可比较”。标准做法是：用唯一分隔符拼成一个新串，比如 str1 + '#' + str2（确保 '#' 不在任一原文中）。
- 拼接后构建后缀数组 SA 和高度数组 height（height[i] 表示 SA[i] 和 SA[i−1] 对应后缀的最长公共前缀长度）
- 遍历 height 数组，只关注那些满足条件的 i：SA[i] 和 SA[i−1] 的起始位置分别落在 str1 和 str2 区域内（即一个 ≤ len(str1)−1，另一个 ≥ len(str1)+1）
- 这些位置对应的 height[i] 中的最大值，就是最长公共子串长度；对应子串可从原串中切出
不依赖 height 数组的简化验证法
若暂不实现 height，仍可用后缀数组快速定位候选子串：
- 对拼接串 S 构建 SA 后，相邻后缀若起始点分属不同原串，它们的公共前缀一定是某对公共子串
- 逐对检查 SA 中相邻项：若 SA[i] 在 str1 区间、SA[i−1] 在 str2 区间（或反之），就计算这两个后缀的 LCP 长度（从头逐字符比对）
- 记录所有 LCP 长度的最大值，并保存其起始位置和所属原串，即可还原子串内容
- 该方式空间省、逻辑直白，虽最坏达 O(n²)，但实践中因公共前缀通常很短，实际效率尚可
关键细节与避坑提示
实际编码时容易忽略但影响结果的几点：
- 分隔符必须唯一且不可出现在任一输入中：否则跨串匹配会误判（如用 'a' 分隔 "ab" 和 "ac"，可能错误匹配出 "a"）
- 高度数组不是必需，但极大提升效率：完整实现 height 可将最长公共子串查找优化至 O(n)，推荐用 Kasai 算法在线性时间内求出
- 子串还原要小心越界：拿到最长 LCP 长度 L 和起始位置 pos 后，需判断 pos 属于 str1 还是 str2，再从对应变量中切片，而非从拼接串中直接取
- 若扩展到多个文本变量（如 str1/str2/str3），只需增加分隔符种类（如 '#', '$', '%'），并在验证时确保所有 N 个串各至少贡献一个后缀参与当前 LCP 段
