# 1. KMP 的 next 数组如何用"最长真前后缀"避免回溯 A next 求法需要 O(m²) B next 数组用于回退文本指针 C KMP 失配时从头重比 D next[i] 是最长真前后缀长度，失配时滑动模式到该处避免回溯 ✓ 正确答案
# 2. Z 函数与 KMP 在"字符串匹配"上的等价与实现差异 A Z 函数无法用于匹配 B 两者等价，Z 用 Z-box 维护最右区间，KMP 用 next 递推，均 O(n+m) ✓ 正确答案 C KMP 用分隔符拼串 D 两者复杂度不同
# 3. height 数组如何求"最长公共子串/不同子串个数" A 不同子串数 = Σheight B 不同子串数 = n(n+1)/2 − Σheight，最长公共子串用跨串相邻 height 最大值 ✓ 正确答案 C height 无法求最长公共子串 D 最长重复子串等于 height 最小值
# 4. 字符串哈希与 KMP/Z 在可靠性与速度上的互补 A 哈希完全替代 KMP B 哈希快但可碰撞，KMP/Z 确定无碰撞，按可靠性/速度需求互补 ✓ 正确答案 C KMP 有碰撞 D 两者都不可靠
# 5. CLRS 第 33 章后缀数组的倍增构造与 LCP 数组 Kasai 算法的工程价值？ A 两者无法配合 B 倍增构造是 O(n) C Kasai 需要 O(n log n) D 倍增 O(n log n) 构建 SA 直观，Kasai O(n) 构建 LCP，是工程常用组合 ✓ 正确答案
# 6. Factor Oracle 在伪周期与子串检测的工程应用。 A FO 只能离线 B FO 精确接受全部因子 C 线性大小、在线构建，近似因子集，用于伪周期与快速子串检测 ✓ 正确答案 D FO 与 AC 等价
# 7. KMP 在"最短循环节 = n - next[n]"结论的证明 A 最短循环节 = n − next[n]（当 n 整除该值时），由 border 与周期互补得到 ✓ 正确答案 B 最短循环节 = next[n] C 与 next 无关 D 最短循环节恒为 1
# 8. fail 指针（后缀链接）为何等价于 KMP 的 next 在 Trie 上的推广 A fail 与 next 无关 B fail 指向最长真后缀，是 KMP next 在多模式 Trie 上的推广 ✓ 正确答案 C fail 指向最长前缀 D 单模式时 fail 不存在
# 9. manacher 算法如何 O(n) 求每个中心的最长回文半径 A 无法处理偶回文 B 每个中心都要 O(n) 扩展 C Manacher 复杂度 O(n²) D 用最右回文区间的对称性初始化半径，r 单调增使总扩展 O(n) ✓ 正确答案
# 11. 最长回文子串在 manacher/PAM/后缀数组三种解法对比 A PAM 无法求最长回文 B Manacher 复杂度 O(n²) C Manacher 最轻量、PAM 功能全、SA 紧凑但复杂，均 O(n) ✓ 正确答案 D SA 方案最简单
# 12. 构建 fail 指针的 BFS 过程及为何沿 fail 可继承匹配状态 A fail 指向最长前缀 B fail 用 DFS 构建 C BFS 保证父先于子，fail 指向最长真后缀使失配可继承已匹配后缀 ✓ 正确答案 D 失配时需回退文本
# 13. AC 自动机如何在 O(n + m + 命中) 内扫描文本找出所有模式 A 每个字符需回退文本 B AC 扫描 O(n·m) C 命中计入 O(n) 不算 D 文本每字符 O(1) 摊还，总 O(n+m+命中) ✓ 正确答案
# 14. SAM 如何在 O(n) 内统计本质不同子串数与出现次数 A 出现次数用转移累加 B 不同子串数需枚举 C 不同子串数 = Σ(len−len(link))，出现次数用 link 树累加，均 O(n) ✓ 正确答案 D SAM 无法统计出现次数
# 15. 多模式匹配在敏感词过滤与入侵检测中的工程运用 A AC 线性扫描支持敏感词过滤与 IDS 特征匹配 ✓ 正确答案 B 敏感词过滤需 O(n²) C IDS 用单模式匹配 D AC 无法处理大模式库
# 16. 如何利用 Z 函数检测字符串的 Border 与周期 A Z[i]==n−i 表示 border，Z[k]≥n−k 且整除表示周期 ✓ 正确答案 B Z 函数无法判 border C 周期判定需 O(n²) D border 与 Z 无关
# 17. 字符串算法在 DNA/基因组（大量重复）场景的特殊处理 A 重复区无需处理 B 直接用后缀树即可 C 用 FM-Index/SA-IS 压缩索引与线性构造应对大文本+大量重复 ✓ 正确答案 D 基因组无法用后缀数组
# 18. 用 Z 函数在 O(n+m) 内做模式串在文本中的所有出现 A Z 匹配复杂度 O(nm) B 需哈希确认识别 C 拼 P#T 后 Z[i]≥|P| 即文本 i 处命中，总 O(n+m) ✓ 正确答案 D 分隔符不必要
# 19. Compact DAWG（CDAWG）在因子自动机的压缩。 A CDAWG 是 O(n²) 空间 B CDAWG 比 DAWG 状态更多 C CDAWG 无法做因子检索 D CDAWG 压缩无分支路径，状态 ≤2n−1，紧凑支持因子检索 ✓ 正确答案
# 20. DAWG 在后缀自动机的等价关系证明。 A 两者构造不同 B DAWG 状态多于 SAM C DAWG 不接受全部子串 D SAM 正是 DAWG（接受所有子串的最小 DFA），endpos 等价类保证最小性 ✓ 正确答案
# 21. Factor Oracle 与 AC 自动机在音乐检索、DNA 拼接的取舍。 A 两者等价 B FO 精确匹配 C AC 用于近似检索 D FO 近似在线适合音乐检索，AC 精确线性适合精确模式检测 ✓ 正确答案
# 22. DC3 / SA-IS 等线性构造后缀数组的复杂度意义 A 倍增与线性等价 B 线性构造需要 O(n log n) C SA-IS 常数更大 D DC3/SA-IS 实现 O(n) 构造，去掉 log n 因子，适合超大文本 ✓ 正确答案
# 23. PAM 的 fail 指针指向"最长回文后缀"的构造思路 A fail 链需 O(n²) B fail 指向最长前缀 C PAM 的 fail 与回文无关 D fail 指向最长真回文后缀，沿 fail 链扩展新回文，构建 O(n) ✓ 正确答案
# 24. 后缀数组与后缀自动机各自擅长的查询类型对比 A SA 擅长在线构建 B SA 擅长静态索引+组合查询，SAM 擅长在线构建+endpos 统计 ✓ 正确答案 C SAM 擅长模式定位 D 两者功能完全不同
# 25. 后缀数组（SA）的排名与 height 数组的含义及用途 A height 无用途 B height 是后缀的排名 C rank 记录相邻 LCP D SA 排序后缀、rank 是逆排序、height 记录相邻 LCP，支撑多种子串查询 ✓ 正确答案
# 26. 后缀树与后缀数组的关系（后缀树叶子按 SA 排列） A 后缀树叶子与 SA 无关 B 后缀树叶子按字典序排列即 SA，内部节点对应 height 的 LCP 区间 ✓ 正确答案 C 内部节点对应最长后缀 D SA 无法表示后缀树
# 27. 回文自动机如何在线（边读边建）统计回文子串 A PAM 构建 O(n²) B PAM 需离线构建 C PAM 无法统计出现次数 D PAM 边读边建，addChar 摊还 O(1)，在线统计回文子串 ✓ 正确答案
# 28. 回文自动机（PAM）如何用两棵树表示奇/偶长度回文 A 偶根（len=0）与奇根（len=−1）两棵树统一处理奇偶回文 ✓ 正确答案 B 只有一个根 C 奇根 len=0 D 双根使状态数 O(n²)
# 29. 用后缀数组 + RMQ 求任意两后缀 LCP 的方法 A 任意两后缀 LCP = 区间 height 最小值，稀疏表 O(1) 查询 ✓ 正确答案 B LCP 需逐字符比较 C 稀疏表查询 O(log n) D LCP 与 height 无关
# 30. AC 自动机上 DP（如"最少替换使包含某模式"）的建模 A DP 无法用 AC 状态 B 状态为 AC 结点，转移读字符施加代价，fail 自动处理模式重叠 ✓ 正确答案 C 转移需回退文本 D AC 只能用于匹配
# 31. AC 自动机与 Aho-Corasick 的 output 链接优化细节 A output 链接直接指向 fail 链首个命中节点，输出 O(命中数) ✓ 正确答案 B 输出需遍历整条 fail 链 C output 链接与 fail 无关 D 命中无法输出
# 32. SAM 的 parent 树（link 树）与 endpos 集合大小计算 A link 树使 endpos 为子树并集，自底向上累加得出现次数 ✓ 正确答案 B endpos 需枚举 C link 树与出现次数无关 D 累加是 O(n²)
# 33. Z 函数（Z-algorithm）如何求每个后缀与整串的 LCP A Z[i] 是后缀 i 与整串的 LCP，Z-box 复用使 O(n) 计算 ✓ 正确答案 B Z[i] 是前缀的 LCP C Z 计算 O(n²) D Z-box 使复杂度退化
# 34. 为何 Z 函数对"周期性/循环节"判定尤其方便 A 周期与 Z 无关 B 周期判定需枚举 C Z 无法判周期 D Z[p]≥n−p 且 n%p==0 判循环节，Z 数组直接暴露周期信息 ✓ 正确答案
# 35. 为何 fail 树（fail 指针反向）利于统计"各模式被命中次数" A fail 树使命中继承成子树累加，自底向上求和各模式命中次数 ✓ 正确答案 B 命中需逐级枚举 C fail 树无法统计 D 累加是 O(n²)
# 36. 后缀自动机（SAM）每个状态代表等价 endpos 类的思想 A endpos 类无法合并 B 状态与 endpos 无关 C 状态数可到 n² D 每个状态是一个 endpos 等价类，类内子串互为后缀且长度连续 ✓ 正确答案
