题干与适用场景
后缀数组保存文本每个后缀的起点，并按后缀的字典序排列。固定文本会收到很多模式查询时，可以在这个有序索引上找出所有匹配，而不用每次从头扫描。Stanford 的 CS166 题目直接要求实现 searchFor，返回所有匹配位置并达到 O(n log m + z) 的查询目标；这里用 m 表示模式长度、n 表示文本长度、z 表示结果数。
面试官考察点
- 能否说明“模式出现”等价于“某个后缀以模式为前缀”。
- 能否用 lower bound 找到匹配区间的左右边界，而不是找到一个位置就停止。
- 能否把构建成本与每次查询成本分开，并正确处理 z 个输出。
- 能否识别空模式、哨兵、重复后缀和字符比较成本等边界。
回答前需要澄清的问题
- 文本是否固定、查询是否很多？若文本也持续变更，后缀数组的重建成本可能不合适。
- 需要返回所有起点、出现次数，还是只判断是否存在？
- 是否区分大小写、Unicode 规范化或字节序列？比较函数必须和业务语义一致。
- 是否已给出 sa，还是也要实现构建？若要构建，允许教学用排序还是要求线性算法？
30 秒回答框架
“后缀数组按后缀字典序排列，所以以 pattern 开头的后缀一定是连续区间。我写一个比较函数，把 pattern 与 text[sa[i]:] 按前缀比较；第一次二分找不小于 pattern 的位置，第二次找大于该前缀的右边界。区间内每个 sa 值就是一个匹配起点，扫描输出成本是 O(z)，查询总成本 O(m log n + z)。空模式按约定返回 n+1 个位置。”
分步骤深入解答
第一步：建立后缀数组的语义
文本 banana 的后缀起点按字典序可写为 [5, 3, 1, 0, 4, 2]。数组只保存整数起点，不复制后缀内容。MIT 讲义强调它是按字典序排列的起点列表，并可在该序列上二分。
第二步：把匹配变成区间
所有以 ana 开头的后缀会相邻，因此答案不是一个点，而是一个半开区间 [left, right)。比较器只需区分三种结果：当前后缀的前缀小于 pattern、相等、或大于 pattern。相等时向左或向右继续收缩，才能得到完整区间。
第三步：实现两个 lower bound
第一个 lower bound 的条件是“后缀前缀不小于 pattern”。第二个可以把比较目标定义为“后缀前缀严格大于 pattern”，或先找相等区间右端。不能直接把 pattern 当成完整后缀比较；短后缀是 pattern 的前缀时，比较结果应视为小于。
第四步：复杂度与构建选择
若 sa 已给出，每次比较最多检查 m 个字符，二分进行 O(log n) 次，因此查询是 O(m log n + z)。Stanford 题目明确把输出成本单列为 O(z)。教学代码用 sorted(range(n), key=text[i:]) 便于理解，但会复制后缀并很慢；生产应采用 prefix-doubling、SA-IS 或成熟库。MIT 和 Stanford 的课程材料都把后缀数组定位为比后缀树更省指针空间的固定文本索引。
可运行的 Python 实现
def build_suffix_array(text):
# 教学构建：便于验证，不代表生产级构建复杂度。
return sorted(range(len(text)), key=lambda start: text[start:])
def compare_suffix_prefix(text, start, pattern):
suffix = text[start:]
prefix = suffix[:len(pattern)]
if prefix < pattern:
return -1
if prefix > pattern:
return 1
if len(suffix) < len(pattern):
return -1
return 0
def search_with_suffix_array(text, suffix_array, pattern):
if pattern == "":
return list(range(len(text) + 1))
def lower_bound(strict):
lo, hi = 0, len(suffix_array)
while lo < hi:
mid = (lo + hi) // 2
cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
take_right = cmp < 0 or (strict and cmp == 0)
if take_right:
lo = mid + 1
else:
hi = mid
return lo
left = lower_bound(strict=False)
right = lower_bound(strict=True)
return sorted(suffix_array[left:right])代码把构建和查询分开；最后排序只是为了按文本出现位置返回结果，若调用方接受后缀数组顺序可省略。空文本、空模式、无匹配和重复匹配都可以直接测试。
高质量示范回答
“我会先确认文本固定且模式很多，然后把每个后缀的起点按字典序存入 sa。由于同一模式是后缀的共同前缀，所有匹配会形成连续区间。我用两个 lower bound 找区间左右边界，比较时只看模式长度并把短后缀当作更小。给定 sa 的查询复杂度是 O(m log n + z)，其中 z 是输出数量；空模式返回 n+1 个边界位置。教学构建可用排序，但大文本要用 prefix-doubling、SA-IS 或成熟实现，并把字符规范化规则固定下来。”
常见错误
- 找到第一个匹配就返回 → 漏掉相邻重复后缀 → 二分左右边界并输出整个区间。
- 用完整后缀字符串和 pattern 直接比较 → 短后缀边界错误 → 明确前缀比较和短后缀规则。
- 把构建复杂度算进每次查询 → 无法解释固定文本场景 → 单独报告一次性构建与每次查询。
- 返回 sa 区间却声称是文本顺序 → 调用方结果顺序不稳定 → 需要时按起点排序或说明顺序契约。
- 忘记空模式的 n+1 个位置 → 与约定不一致 → 在入口先处理空模式。
追问及应对
如果模式长度 m 很大，如何减少重复字符比较？
给相邻后缀补 LCP 信息，并在二分时复用已知公共前缀。这样可以把查询优化到接近 O(m + log n)，但要额外维护 LCP 与更复杂的搜索不变量；没有该增强时应诚实保留 O(m log n)。
文本会频繁更新时还用后缀数组吗？
不应把静态索引硬套到高频写入。可批量重建、按段维护多个索引再合并，或选择在线匹配结构。决策取决于更新频率、查询量和可接受的重建延迟。
如何验证二分边界没有漏结果？
对随机小文本与模式，用暴力扫描结果和 searchwithsuffix_array 对比；覆盖空模式、重复字符、模式比文本长、无匹配和所有位置都匹配。边界断言应检查区间外相邻后缀不满足前缀条件。
为什么不能直接用 KMP？
若只有一个模式且文本一次性读取，KMP 更直接，时间 O(n+m)。后缀数组的优势在固定文本、多模式查询，以及还要支持重复子串、LCP 或 BWT 等离线索引操作时。