# 1. AC 自动机的 fail 指针为何用 BFS 构造？若用 DFS 会导致什么问题 A fail 指针可以用 DFS 构造，因为 DFS 也保证深度顺序 B fail 指针无需区分 BFS 还是 DFS，结果相同 C fail 指针用 BFS 构造，因为需要保证深度递增，使父节点的 fail 已就绪 ✓ 正确答案 D fail 指针指向节点的最长前缀节点
# 2. Rabin-Karp 滚动哈希的冲突概率分析中模数取大素数 p 时，两个不同字符串哈希碰撞的概率 ≤ L/p，双哈希如何把冲突概率降到可忽略 A 两个不同字符串碰撞概率恒为 1，与模数无关 B 模数越大碰撞概率越高 C 碰撞概率 ≤ L/p，其中 p 是模数，双哈希把概率相乘降到可忽略 ✓ 正确答案 D 双哈希在同一模数下做两次，能完全消除碰撞
# 3. Aho-Corasick 自动机如何由 Trie + fail 指针实现多模式匹配？说明 goto/failure/output 三表的构造与扫描过程，复杂度 O(n+m+z)（z 为命中数） A 扫描时每个字符都走 goto 并沿 fail 跳转，总复杂度 O(n+m+z) ✓ 正确答案 B 扫描复杂度为 O(n·m)，n 为文本长度、m 为模式数 C fail 指针用 DFS 构造 D output 表只记录当前节点的直接命中，无需 fail 链
# 4. Rabin-Karp 在二维模式匹配（矩阵中找子矩阵）中的扩展中先对每行做滚动哈希，再对列做滚动哈希 A 二维匹配无法用哈希，只能逐格比较 B 二维哈希完全没有碰撞 C 每行先做哈希后，列处理就无需再做 D 先对每行、再对每列做滚动哈希，可对任意子矩阵 O(1) 求哈希 ✓ 正确答案
# 5. 滚动哈希在子串比较中的'滑动'过程中 H[i+1..j+1] = (H[i..j] - s[i]·p^{j-i})·p + s[j+1] mod M，为何要预计算 p^k mod M A 滑动一位需要 O(log n) 时间，因为要快速幂 B 滚动哈希无需模数也能保证无碰撞 C 滑动公式中无需减去首位字符的贡献 D 预计算 p^k 是为了 O(1) 取幂，保证滑动 O(1) 更新 ✓ 正确答案
# 6. Boyer-Moore 坏字符表的构建中 last occurrence 数组如何支持跳跃，字符集为 Unicode 时如何用哈希表代替定长数组？ A 坏字符表用定长数组记录每个字符第一次出现的位置 B last occurrence 记录字符的最早出现位置用于跳跃 C 坏字符规则让匹配从最左到最右顺序扫描，无法跳跃 D Unicode 字符集下用哈希表存储字符最后出现位置，避免大数组 ✓ 正确答案
# 7. AC 自动机的 fail 树中把 fail 边反向成树后，如何用 DFS 序加树状数组支持在线文本扫描中动态统计各模式出现次数 A fail 树中一个节点的后代代表其后缀 B fail 树与 Trie 结构完全相同 C 用 DFS 序把子树映射为连续区间，配合 BIT 可在线统计模式出现次数 ✓ 正确答案 D 在线统计必须重新扫描文本才能得到模式次数
# 8. 双向滚动哈希判回文中同时维护正反两个哈希就能 O(1) 判断任意子串是否回文，与 Manacher 的取舍 A 双向哈希无需预处理即能判断任意子串 B 双向哈希判回文有碰撞概率，需双哈希降低，Manacher 则无碰撞 ✓ 正确答案 C Manacher 比双向哈希更慢，因为要 O(n log n) D 双向哈希不能 O(1) 判回文，必须 O(n) 比较
# 9. 为何 KMP 的 next 数组比 BM 的坏字符表更'稳定'（不依赖字符集大小） A next 数组依赖字符集大小，构建空间随字符集增长 B 两者都依赖字符集大小 C BM 坏字符表与字符集完全无关 D next 数组只依赖模式串内部结构，与字符集无关，更稳定 ✓ 正确答案
# 10. Boyer-Moore 的坏字符规则与好后缀规则为何在英文/随机文本实践中平均达到 O(n/m)？最坏情况为何仍是 O(n+m) A BM 的平均复杂度和最坏复杂度都是 O(n/m) B BM 从模式串开头向后匹配，无法跳跃 C BM 最坏情况是指数级 D 坏字符规则在英文/随机文本中能大幅跳跃，平均接近 O(n/m) ✓ 正确答案
# 11. 多模式匹配的字典规模选型中模式集从几十到百万时，KMP/AC 自动机/正则引擎/位并行（Shift-And）各自的适用边界？ A 模式多时用 KMP 逐个匹配最合适 B Shift-And 位并行适合任意长度的模式 C 正则引擎在大字典下总是最快的 D 模式规模大且共享前缀多时用 AC 自动机最合适 ✓ 正确答案
# 12. AC 自动机的内存优化中完整 goto 表在字符集大时爆炸，如何用稀疏表、双数组（Double-Array Trie）或动态分配压缩？ A 字符集大小不影响 goto 表的空间 B 双数组 Trie 的空间是 O(N·S)，比完整表更大 C 稀疏表比完整表占用更多空间 D 完整 goto 表 next[N][S] 在字符集大时空间 O(N·S) 会爆炸 ✓ 正确答案
# 13. Rabin-Karp 的误报处理中哈希碰撞导致误匹配时如何二次验证，多模式场景下'哈希候选过滤+精确比对'的框架如何设计？ A 哈希相等即认为匹配，无需二次验证 B 双哈希能完全消除误报，无需精确比对 C 多模式场景下哈希过滤无法减少候选 D 哈希碰撞导致误报，需在哈希相等时再做精确比对确认 ✓ 正确答案
# 14. 字符串哈希的碰撞攻击中固定底数与模数可被构造碰撞（生日攻击），随机化底数与双哈希如何防御 A 固定底数与模数时攻击者无法构造碰撞 B 生日攻击需要 O(p) 个哈希才能碰撞，与 √p 无关 C 随机化底数与双哈希可以显著提高构造碰撞的难度 ✓ 正确答案 D 双哈希是唯一能防御碰撞的方法
# 15. 模式串含通配符 ? 的多模式匹配中为什么 AC 自动机会退化，常用 FFT 卷积或位并行替代的原理 A FFT 卷积与位并行（Shift-And）可处理通配符，避免 AC 退化 ✓ 正确答案 B AC 自动机对通配符依然高效，不会退化 C 通配符只影响模式长度，不影响匹配算法 D 位并行任意长度都高效
# 16. KMP、Rabin-Karp、Boyer-Moore 在单模式/多模式/流式场景的选型中各自优势与不适用场景 A 多模式匹配应升级为 AC 自动机，KMP/BM 逐个匹配效率低 ✓ 正确答案 B Boyer-Moore 最适合流式在线匹配 C Rabin-Karp 最坏情况是 O(n+m)，不会退化 D KMP 不适合单模式匹配
# 17. 多模式匹配在敏感词过滤中的工程部署中 AC 自动机的内存占用与模式库更新策略 A 模式库更新时必须全量重建，无法避免停顿 B 敏感词过滤无需处理字符集大小 C 可用双数组 Trie 优化内存，并用双缓冲/原子切换实现模式库更新 ✓ 正确答案 D AC 自动机无法一次扫描命中所有敏感词
# 18. 滚动哈希实现的常见误区中负数取模、未预计算 p^k、比较时漏掉长度信息、双哈希共用模数等，分别会导致什么问题？ A 未预计算 p^k 只影响常数，不影响复杂度 B Java 负数取模结果仍为负，需先加模数再取模 ✓ 正确答案 C 比较哈希时无需关心长度是否相同 D 双哈希共用模数不影响碰撞概率的独立性
# 19. 多模式匹配的流式场景中文本不能一次性读入时如何增量维护匹配状态（AC 的输出状态持久化），与分块处理的边界问题？ A 流式处理必须重新扫描整段文本 B AC 流式处理只需持久化当前状态，跨块时用重叠缓冲保证不漏匹配 ✓ 正确答案 C 模式串不会跨块边界，无需处理 D 流式场景下 AC 无法维护匹配状态
# 20. Aho-Corasick 的 output 链接中沿 fail 链逐层收集命中会退化，用字典后缀链接（dictionary suffix link）如何一次性收集全部命中？ A 沿 fail 链逐层收集命中总是 O(1)，不会退化 B 字典后缀链接让命中数 z 变多 C 字典后缀链接只记录 fail 链上最近的命中节点，收集开销与命中数 z 成正比 ✓ 正确答案 D output 收集与 z 无关，复杂度固定
# 21. KMP 自动机中把 next 数组补全成确定性转移表后如何做到 O(n) 流式扫描且每字符只处理一次，与 AC 的关系 A KMP 自动机每字符仍需 while 回溯，无法流式 B KMP 自动机把 next 补全为确定性转移表，扫描时每字符 O(1) 处理 ✓ 正确答案 C AC 自动机与 KMP 自动机无关 D 补全转移表会提高扫描复杂度到 O(n log n)
