KMP 的 next 数组如何用"最长真前后缀"信息避免匹配时的回溯？
KMP 预处理模式串得到 next[i]（= π[i]），表示前缀 s[0..i] 的最长真前后缀长度。匹配时若文本字符与模式字符失配，不是回退文本指针，而是用 next 把模式串"滑动"到最长真前后缀已匹配的位置继续，从而避免重复比较已匹配的字符。文本指针只前进不退，模式指针按 next 跳转，总复杂度 O(n+m)。next 的求法用"自身匹配"（next[i] 由 next[i-1] 递推），也是 O(m)。
next 数组记录了"已匹配后缀的最长真前缀"，失配时模式可安全滑到该前缀处，因为前缀已与后缀相同，无需重比。这是 KMP 线性时间的核心。
Z 函数与 KMP 在字符串匹配上的等价性与实现差异是什么？
Z 函数 Z[i] 表示 s 与后缀 s[i:] 的 LCP。两者等价：对模式 P + 文本 T 构造串 S = P + "#" + T，则 Z 函数在 T 部分 Z[i] ≥ |P| 的位置即 P 出现处；KMP 的 next 也记录匹配信息，两者可互相转换。实现差异：Z 函数用"Z-box 维护最右匹配区间"直接推导，KMP 用 prefix function 递推（next 数组）；匹配时 Z 用分隔符拼串后扫一遍，KMP 直接边匹配边用 next 跳转。两者都是 O(n+m) 线性，常数与实现风格不同。
Z 与 KMP 都利用"串自身匹配"信息避免重复，但视角不同：Z 从"头部 LCP"出发，KMP 从"尾部最长前后缀"出发。实现差异在于 Z-box 与 next 数组的维护。
height（LCP）数组如何求最长公共子串与本质不同子串个数？
height 数组（LCP array）记录相邻后缀的 LCP。最长公共子串：把两串拼接（含分隔符），SA 后扫描相邻跨串后缀，height 的最大值即最长公共子串长度。本质不同子串数 = 总子串数 − Σ height = n(n+1)/2 − Σ_{i} height[i]（因为相邻后缀的 LCP 是重复的公共前缀）。最长重复子串 = max height。三者都可用 SA+height 在 O(n) 内回答。
height 数组编码了"相邻后缀的重叠"，任意后缀对的 LCP 是区间 min，不同子串计数把重复前缀扣除，最长公共子串用跨串扫描。SA+height 一步到位。
字符串哈希与 KMP/Z 在可靠性与速度上的互补关系？
字符串哈希（滚动哈希）O(1) 更新、速度快，但存在碰撞概率（可能误判相等）；KMP/Z 是确定性算法，无碰撞但需 O(n) 预处理、常数较大。互补：哈希用于快速筛选/近似比较（如滚动哈希判等、子串哈希），KMP/Z 用于需要精确、无碰撞结果的匹配/周期/边界问题。工程上常对哈希碰撞做逐字符确认，或在大规模用哈希提速、小规模/关键路径用 KMP/Z 保证正确。可靠性与速度的取舍决定选用。
哈希快但概率、KMP/Z 确定但重。互补策略：哈希先行 + 确定性确认，或按需求选型。这是字符串处理中"概率 vs 确定性"的经典权衡。
CLRS 第 33 章后缀数组的倍增构造与 LCP 数组 Kasai 算法的工程价值？
后缀数组的倍增构造：按长度 1,2,4,... 对各前缀排序，用二元组（rank, rank+len）排序合并，O(n log n)，实现简单、易理解。Kasai 算法用"相邻后缀 LCP ≥ 前一个 LCP−1"性质 O(n) 构造 height 数组。工程价值：倍增法实现直观、无需复杂诱导排序，适合中小规模；配 Kasai 的 O(n) height，可完成最长重复子串、不同子串计数、模式匹配等查询，是竞赛与教学的标准组合。
倍增构造 + Kasai 提供"易实现 + O(n) LCP"的工程组合，虽非最优常数但表现稳定、易调试，是 SA 应用的入口。
Factor Oracle 在伪周期与子串检测的工程应用是什么？
Factor Oracle（因子甲骨文）是一种线性大小、可在线构建的自动机，接受比真实因子集更大的语言（含"伪因子"），用于快速近似子串检测与模式归纳。工程应用：伪周期检测——用 FO 的"因子"近似判断文本的周期性/重复结构；子串检测——文本流中快速判断某串是否可能为子串（FO 的转移可近似匹配，允许少量误差）。它比 SA/AC 更省内存、在线构建，适合音乐检索、DNA 快速扫描等需近似的场景。
Factor Oracle 用"有损但线性"的自动机近似因子集，牺牲精确性换速度与在线构建。工程上用于需要快速、近似子串检测与结构归纳的场合。
证明 KMP 中"最短循环节 = n − next[n]"这一结论？
设 s 长度 n，next[n] 是最长真前后缀长度。若 s 有周期 p（即 s[i]=s[i+p]），则 s 有长度为 n−p 的 border（前缀等于后缀）。最短循环节即最小周期 p。当 n 能被 p 整除时，s 由 n/p 个 p 长的块重复构成，此时 p 是最短周期当且仅当 n−p 是最长 border（next[n]）。因此最短循环节 = n − next[n]（当 n % (n−next[n]) == 0 时）。证明：border 长度 n−next[n] 对应周期 next[n]... 实际最短周期 p = n − next[n]，且需 n 整除 p 才为完整重复。
周期与 border 互为补集：周期 p ⇒ 有 n−p 的 border。最长 border 对应最短周期。故最短循环节 = n − next[n]（需整除），这是 KMP 找循环节的标准结论。
fail 指针（后缀链接）为何等价于 KMP 的 next 在 Trie 上的推广？
KMP 的 next 指向"当前匹配前缀的最长真前后缀"，用于单模式匹配时的失配跳转。AC 自动机的 fail 指针指向"当前 Trie 节点代表串的最长真后缀"，恰是 next 在 Trie 上的推广：单模式时 Trie 退化为一条链，fail 指针退化为 next 数组。多模式时，fail 把"最长真后缀"扩展到整棵 Trie，失配时沿 fail 跳到已匹配的最长后缀节点继续，避免回溯。因此 fail = next 的多模式推广。
next 是"单串的最长真border"，fail 是"多串 Trie 的最长真后缀"，单模式时一致。fail 的 BFS 构造与 next 的递推同构，都是"复用已匹配后缀"。
Manacher 算法如何 O(n) 求每个中心的最长回文半径？
Manacher 维护当前最右回文 [l,r] 及中心 c。对每个中心 i，若 i≤r，用对称点 j=2c−i 的半径初始化 d[i]=min(d[j], r−i)；否则从 0 开始。然后向外扩展（比较 s[i−k] 与 s[i+k]），扩展后若 r 变大则更新 l,r,c。每个位置最多扩展一次（r 单调增），总 O(n)。奇/偶回文用 d1, d2 分别处理（或间隔符 #）。最长回文半径即 max d。
关键是用"已知回文覆盖区 [l,r]"的对称性初始化新中心半径，避免重复扩展。r 单调递增保证每个字符最多被扩展一次，是线性上界成立的原因。
如何利用回文结构做本质不同回文子串计数？
本质不同回文子串计数用回文树（PAM/Eertree）：PAM 的每个状态对应一个本质不同的回文子串，构建时新建状态即新增一个回文。因此本质不同回文子串数 = PAM 的状态数 − 2（去掉奇偶根）。在线构建时每次 addChar 新建的状态数累加即答案。性质：本质不同回文子串数 ≤ n（字符串长度），PAM 状态 O(n)。这是回文树的核心应用。
回文树状态与回文子串一一对应，新建状态即新回文，故计数 = 状态数。线性构建 O(n) 直接得到本质不同回文子串数。
最长回文子串在 Manacher、PAM、后缀数组三种解法上的对比？
最长回文子串三种解法：Manacher 用中心扩展+对称复用 O(n)，最直接、常数小。PAM 构建时记录最长回文节点 O(n)，功能更全（可统计回文）。后缀数组：把串反转拼接，对每个中心用"正串与反串后缀的 LCP"（RMQ）求回文半径，O(n log n) 或 O(n)，但需 SA+RMQ，实现复杂。对比：Manacher 最简单快、PAM 功能全、SA 空间紧凑但实现复杂。需求是"最长回文"推荐 Manacher，需统计/在线用 PAM。
三法都 O(n)（近似），但实现与常数不同。Manacher 轻量、PAM 多功能、SA 紧凑但复杂，选型取决于需求。
AC 自动机构建 fail 指针的 BFS 过程，以及为何沿 fail 可继承匹配状态？
AC 自动机 fail 指针用 BFS 从根开始构建：根的子节点 fail 指向根；对每个节点 u 的字符 c 子节点 v，沿 u 的 fail 链找"有字符 c 转移"的节点，v 的 fail 指向该转移节点；若无则 v 的 fail 指向根。BFS 保证处理 v 时父节点的 fail 链已就绪。沿 fail 可继承匹配状态：因为 fail 指向"最长真后缀"，若当前节点代表的前缀已匹配，其 fail 后缀必已匹配（是文本后缀），故沿 fail 找失配转移时无需回溯，直接继承已匹配的后缀状态，继续匹配。
BFS 满足"父先于子"的 fail 依赖；fail 指向最长真后缀使失配时"已匹配的后缀"仍有效，可继承匹配状态，这是 AC 线性扫描的关键。
AC 自动机如何在 O(n + m + 命中) 内扫描文本找出所有模式？
AC 自动机扫描文本：从根出发，对每个文本字符，若当前状态有该字符转移则走；否则沿 fail 链找到有转移的状态（或回根）再走；每到达一个状态，检查 output 并输出该状态及其 fail 链上所有命中模式。文本每个字符走 O(1)（平均滑动，fail 链总滑动 O(n)），总匹配 O(n)，加上输出命中 O(命中数)。总复杂度 O(n + m + 命中)，其中 m 为模式总长度（构建）。这是多模式匹配的线性保证。
AC 用 fail 链避免回退文本，每个字符摊还 O(1)，输出命中另计。总线性 + 命中数，是多模式匹配的最优线性算法。
SAM 如何在 O(n) 内统计本质不同子串数与出现次数？
SAM 每个状态代表一个 endpos 等价类，含 len 区间 [len(link)+1, len(state)] 的子串。本质不同子串数 = Σ_state (len(state) − len(link(state)))。出现次数：对每个状态，初始把"终态"（包括每个前缀的 endpos）计数为 1，再沿 link 树自底向上累加（子状态出现次数加到父/link 状态），得到每个状态代表子串的出现次数。两者都在 O(n) 内完成（构建 + 拓扑累加）。
SAM 的 len−len(link) 给出每状态新子串数，link 树累加给出现次数。本质不同子串与出现次数都是 SAM 的 O(n) 应用。
多模式匹配在敏感词过滤与入侵检测中的工程运用？
多模式匹配（AC 自动机）用于敏感词过滤：把敏感词建成模式库，对用户文本实时扫描，O(n+命中) 找出/替换所有敏感词。入侵检测（IDS/IPS）：把攻击特征（signature）作为模式，对网络流量/数据包做多模式匹配，检测已知攻击模式。工程上模式库可达 10k–10M 条目，AC 预处理 O(总长度)、内存 O(节点数×字符集)，用压缩/哈希优化。结合实时性要求，用 AC 保证线性扫描吞吐。
AC 的多模式线性匹配是敏感词过滤与 IDS 的基础引擎。工程要点是模式库内存管理与实时扫描吞吐，用 AC 线性保证实现。
如何利用 Z 函数检测字符串的 Border 与周期？
Border 是"既是前缀又是后缀"的子串。Z 函数中，位置 i 是 border 起点当且仅当 Z[i] = n−i（即后缀 s[i:] 与整串的 LCP 等于后缀长度，说明该后缀 = 前缀）。因此所有 border 可由 Z 数组检测：遍历 i，若 Z[i] == n−i 则 s[i:] 是 border。周期：若 n 是 k 的倍数且 Z[k] ≥ n−k，则 k 是周期（用 Z[k] 判断前缀是否重复）。Z 数组 O(n) 给出所有 border 与周期判定。
Z[i]==n−i 精确刻画"后缀等于前缀"的 border；Z[k]≥n−k 刻画周期。Z 数组把所有 border 与周期信息在 O(n) 内给出。
字符串算法在 DNA/基因组（大量重复）场景下的特殊处理？
DNA/基因组字符串含大量重复（重复序列、低复杂度区域），且常达 GB 级。特殊处理：1) 用压缩索引（FM-Index、BWT、后缀数组）降低内存，避免全量后缀树；2) 用 SA-IS/DC3 线性构建应对超大文本；3) 对重复/低复杂度区域用掩码（mask）或特异性过滤，避免误报；4) 用滚动哈希/AC 加速重复 motif 扫描。大量重复导致 SA 高度集中、LCP 大，需用 RMQ 压缩与高效匹配。工程上用流式/内存映射 + 压缩索引处理。
基因组场景核心是"大 + 重复"。用压缩索引（FM-index）省内存、线性构造（SA-IS）处理规模、掩码过滤重复区，是生物信息字符串处理的特殊手段。
用 Z 函数在 O(n+m) 内求模式串在文本中的所有出现位置？
构造串 S = P + "#" + T（分隔符 # 不出现在 P/T），计算 Z 数组。对文本部分的下标 i（S 中从 |P|+1 开始），若 Z[i] ≥ |P|，则模式 P 出现在文本位置 i−|P|−1。因为 Z[i] 是 S 与后缀 S[i:] 的 LCP，≥|P| 说明文本从该位置开始的子串与 P 完全匹配。构建 Z 数组 O(|S|)=O(n+m)，扫描一次得所有出现，总 O(n+m)。
用分隔符把"匹配"化为"Z 函数与整串的 LCP"，Z[i]≥|P| 即命中。这是 Z 函数做匹配的标准方法，线性且无碰撞。
Compact DAWG（CDAWG）在因子自动机的压缩如何实现？
DAWG（有向无环因子图）是接受所有子串（因子）的最小自动机；CDAWG（Compact DAWG）把 DAWG 中"无分支的路径"压缩成带标签的边（类似后缀树压缩），减少状态数。CDAWG 的状态数 ≤ 2n−1，边数 ≤ 3n，比完整 DAWG 更紧凑。压缩实现：把 DAWG 中出度为 1 且入度为 1 的连续转移合并为一条带子串标签的边。CDAWG 保留因子检索能力，内存更省，用于文本索引。
CDAWG 把"路径压缩"应用到 DAWG，合并无分支段，得到线性大小、支持子串检索的紧凑自动机。是 SAM 与后缀树的折中。
DAWG 在后缀自动机的等价关系如何证明？
DAWG（接受所有子串的最小 DFA）与后缀自动机（SAM）等价：SAM 正是接受所有子串的最小确定性自动机，因此 DAWG 与 SAM 是同一对象（SAM 是 DAWG 的构造实现）。证明：构造 SAM 后，它是接受所有子串的 DFA（可达状态对应各子串），且状态数最小（每个状态对应 endpos 等价类，不可再合并），故等于 DAWG。反向，DAWG 的最小化也得到相同结构。等价性建立在"endpos 等价类划分"是最小状态数的依据。
SAM 是 DAWG 的构造名称，二者是同一最小 DFA。证明核心是"endpos 等价类"恰为最小状态划分，不可再约简，故 SAM 即 DAWG。
Factor Oracle 与 AC 自动机在音乐检索、DNA 拼接的取舍？
Factor Oracle 线性、在线构建、近似因子集（含伪因子），适合快速近似匹配与结构归纳（如音乐检索中的旋律相似度、DNA 快速片段扫描），但允许误报。AC 自动机精确多模式匹配、O(n) 线性、适合精确模式检测（敏感词、特征），但需预构建模式库、内存较大。取舍：音乐检索需要容错/近似相似度 → FO；DNA 拼接/精确 motif 检测需要精确 → AC 或 SA。FO 牺牲精确性换速度与在线，AC 保精确性。
FO 近似快、在线，AC 精确线性、需预建。场景需求"近似相似度"用 FO，"精确多模式"用 AC。取舍在精确性与灵活性。
DC3 / SA-IS 等线性构造后缀数组的复杂度意义？
DC3（Skew）与 SA-IS 实现后缀数组的 O(n) 线性构造，比倍增 O(n log n) 更优。意义：对超大输入（GB 级文本、基因组）线性复杂度是必要的（log n 因子在 10^9 量级不可忽视）。DC3 用"模 3 分桶 + 递归 + 合并"，SA-IS 用"诱导排序"，都 O(n) 但常数不同（SA-IS 更小）。复杂度意义：突破 O(n log n) 的排序下界不适用（后缀排序可用线性），使大文本后缀索引构建可行。
线性构造去掉 log n 因子，使超大文本的后缀数组构建可行。DC3/SA-IS 是线性构造的里程碑，SA-IS 常数更优。
PAM（回文自动机）的 fail 指针指向"最长回文后缀"的构造思路？
PAM 的 fail 指针指向当前回文节点的"最长真回文后缀"（即当前回文去掉两端字符后仍为回文的最长者）。构造思路：读入新字符时，从当前最长回文后缀沿 fail 链找"前面字符匹配"的位置，即尝试扩展；若扩展出新回文则新建节点，其 fail 指向沿 fail 链找到的下一个可扩展回文。fail 链提供"所有回文后缀"的候选，保证在线构建 O(n)。这与 KMP/AC 的 fail 类似，但专门针对回文结构。
fail 链枚举所有回文后缀，扩展新回文时沿 fail 找匹配位置。fail 指向最长回文后缀使每次 addChar 摊还 O(1)，构建线性。
后缀数组与后缀自动机各自擅长的查询类型对比？
后缀数组（+LCP）擅长：模式出现次数/定位（二分）、最长公共子串、不同子串计数、LCP/RMQ 查询，适合静态文本的批量查询，空间紧凑、可压缩。后缀自动机擅长：子串出现次数（endpos 统计）、本质不同子串数、在线匹配、最长公共子串（两串）、多模式统计，适合在线/动态构建与统计型查询。对比：SA 适合静态索引+组合查询，SAM 适合在线构建+统计，二者信息等价但操作方式不同。
SA 是"静态索引 + RMQ/LCP"，SAM 是"在线自动机 + endpos 统计"。选型看查询类型（静态批量 vs 在线统计）与内存需求。
后缀数组（SA）的排名与 height 数组的含义及用途？
后缀数组 SA 是后缀按字典序排序后的起始位置序列，rank[i] 是后缀 i 的排名（SA 的逆）。height 数组（LCP array）记录相邻后缀的 LCP：height[i]=LCP(SA[i−1], SA[i])。用途：SA 支持模式匹配（二分区间）、子串排序；rank 用于快速比较后缀；height 用于最长重复子串（max）、不同子串计数（Σ 扣除）、LCP 查询（RMQ）、最长公共子串。SA+rank+height 构成后缀数组的完整功能。
SA 给排序、rank 给排名、height 给相邻 LCP，三者配合实现后缀数组的全部查询。height 是 SA 与后缀树/子串信息的桥梁。
后缀树与后缀数组的关系：后缀树叶子按 SA 排列？
后缀树的叶子按字典序从左到右排列，其顺序正是后缀数组 SA（每个叶子对应一个后缀，排序后即 SA 顺序）。后缀树内部节点的路径标签对应一个 LCP 区间，其叶子集合是 SA 中一段连续区间。SA + height 数组可看作后缀树的紧凑表示：SA 顺序对应叶子，height 数组对应内部节点（LCP 区间）。可从 SA+height 重建后缀树（历史上），二者等价。
后缀树叶子 lb 序 = SA，内部节点 = height 的 LCP 区间。SA+height 是后缀树的紧凑、内存友好的替代，二者同构。
回文自动机（PAM）如何在线（边读边建）统计回文子串？
PAM 在线构建：读入每个字符时，从当前最长回文后缀沿 fail 链扩展，若形成新回文则新建节点并设 fail，同时可更新"出现次数"（新回文出现一次，后续沿 fail 累加）。在线统计：每次 addChar 可得到以当前字符结尾的回文数、累计不同回文数、每个回文的出现次数。整个构建 O(n)（fail 链摊还），边读边建即可完成统计，无需离线。
PAM 的 fail 链支持在线扩展，addChar 摊还 O(1)，边读边建同时统计回文子串。在线性是 PAM 相比 SA/Manacher 的独特优势。
回文自动机（PAM）如何用两棵树表示奇/偶长度回文？
PAM 用两个根分别表示"偶长度根"（空串，len=0）和"奇长度根"（len=−1，虚拟，用于单字符回文），形成两棵"回文树"。偶根子树处理偶长度回文，奇根子树处理奇长度回文。读入字符时，从对应根/当前回文沿 fail 扩展，新建的回文节点挂到相应树上。fail 指向上一个"最长回文后缀"。双根使奇偶回文统一处理，状态数 ≤n，构建 O(n)。
双根（len=0 与 len=−1）统一奇偶回文：奇根 len=−1 使"单字符回文"可视为从 −1 扩展，两棵树分别承载奇偶回文状态。这简化了构建逻辑。
用后缀数组 + RMQ 求任意两后缀 LCP 的方法？
任意两后缀的 LCP：设两后缀排名 r1<r2，则 LCP = min(height[r1+1..r2])，即 LCP 数组区间最小值。用 RMQ（稀疏表 O(n log n) 预处理 + O(1) 查询）可快速回答任意两后缀的 LCP。方法：先建 SA 与 height，对 height 建稀疏表（st[k][i] 存区间最小值），查询时取 k=log(r2−r1)，答案为 min(st[k][r1+1], st[k][r2−2^k+1])。O(1) 查询支撑最长公共子串等。
相邻 height 的最小值 = 任意两后缀 LCP 是 SA 的 RMQ 性质。稀疏表 O(1) 查询使大量 LCP 查询高效。
AC 自动机上 DP（如"最少替换使包含某模式"）的建模？
在 AC 自动机上做 DP：状态为 (AC 结点, 已处理的位置/关键谓词)，转移为读入字符（沿 AC 边）并施加代价。如"最少替换字符使文本包含某模式"：把模式建 AC，DP[状态][已构造前缀] 表示到该状态的最小替换数，转移时对每个字符选"替换代价"（若字符与当前位置匹配则 0 否则 1），沿 AC 转移记录新状态，统计到达模式终态的最小代价。AC 状态编码"已匹配的最长模式前缀"，DP 与 AC 结合可处理"避免/强制包含模式"的约束优化。
AC 状态携带"当前匹配到的模式前缀"信息，DP 在状态上做最优化。AC 的 fail 自动处理模式重叠，DP 转移 O(状态×字符集)，是"AC+DP"的经典建模。
AC 自动机的 output 链接优化细节？
AC 自动机的 output 信息除了"本节点是否命中模式"外，还需通过 fail 链传播"经 fail 后的命中"。优化：构建时预处理 output 链接（直接指向"沿 fail 链第一个有 output 的节点"），这样匹配时无需逐级走 fail 输出，只需沿 output 链接一次输出所有命中。这避免每次匹配遍历整个 fail 链，把输出成本降到 O(命中数)。构建时用 BFS 顺带计算 output 链接，O(总长度)。
output 链接压缩了"fail 链上的命中"为"直接跳转"，使输出命中 O(命中数) 而非 O(链长)。是 AC 效率的工程优化。
SAM 的 parent 树（link 树）与 endpos 集合大小计算？
SAM 的 link（parent）边构成一棵树（link 树/parent 树）：每个节点的 link 指向其最长真后缀状态，形成树结构。endpos 集合大小计算：对每个前缀位置对应的状态标记为 1（终态），然后按 link 树拓扑序自底向上累加（子节点贡献给父节点），得到每个状态代表子串的出现次数（endpos 大小）。这是因为：状态 u 的 endpos 集合 = 其 link 树子树中所有终态位置的并集。累加 O(n)。
link 树把 endpos 集合组织成"子树并集"结构，自底向上累加即得出现次数。这是 SAM 统计出现次数的核心机制。
Z 函数（Z-algorithm）如何求每个后缀与整串的 LCP？
Z 函数 Z[i] 定义为 s 与后缀 s[i:] 的最长公共前缀（LCP）长度，即每个后缀与整串的 LCP。Z-algorithm 在线性时间内计算：维护最右匹配区间 [l,r]，对 i 若 i≤r 用 Z[i−l] 初始化（受 r−i+1 限制），否则从 0 开始，向外扩展比较并更新 l,r。r 单调增，总扩展 O(n)，故 O(n)。Z[i] 直接给出每个后缀与整串的 LCP。
Z[i] 就是"后缀 i 与整串的 LCP"，Z-box 复用已匹配区间使扩展摊还 O(1)，O(n) 求出全部 Z 值。
为何 Z 函数对周期性/循环节判定尤其方便？
Z 函数对周期判定尤其方便：串 s 的周期为 p 当且仅当 p 整除 n 且 Z[p] ≥ n−p（即从位置 p 起与整串匹配至少 n−p 个字符，说明前缀重复）。循环节判定：最短循环节 p 满足 n%p==0 且 Z[p]≥n−p。因为 Z 数组直接给出"每个位置与整串的 LCP"，周期所需的"前缀重复到末尾"用 Z[p]≥n−p 直接判断，无需其他结构。扫描 Z 数组 O(n) 判所有周期。
Z[p]≥n−p 精确刻画"以 p 为步长的周期"，配合整除判循环节。Z 数组把周期信息直接暴露，比 KMP 的 next 更直观便判。
为何 fail 树（fail 指针反向）利于统计各模式被命中次数？
AC 自动机的 fail 指针反向构成 fail 树（树的根为根节点，子节点指向 fail 为父）。匹配时，文本命中某节点 v，则 v 的 fail 链上所有节点（即 v 在 fail 树中的祖先）代表的后缀也被命中。因此统计各模式命中次数：扫描文本时，每到达一个节点 v，给 v 计数 +1；最后按 fail 树自底向上累加（把节点的计数加到其 fail 父节点），得到每个节点（及模式）被命中的总次数。因为 fail 树把"命中继承"变成"子树累加"，O(n) 完成。
fail 树使"命中 v 隐含命中其 fail 祖先"变成树上的包含关系，累加即可。自底向上求和 O(n) 统计所有模式命中次数。
后缀自动机（SAM）每个状态代表等价 endpos 类的思想？
SAM 的核心思想：每个状态代表一个 endpos 等价类——拥有相同"出现结束位置集合"的子串集合。同一状态内的子串互为后缀、长度连续（区间 [len(link)+1, len(state)]），且出现位置完全相同。endpos 等价类划分使状态数 ≤2n−1（线性），因为每个子串的 endpos 只依赖其结尾位置，等价类有限。状态=endpos 等价类正是 SAM 的可持续化与最小性的来源。
endpos 等价类是 SAM 的基石：状态=endpos 类，link 指向最长后缀所在类，len 界定类内长度。这保证状态数线性、支持子串计数与匹配。
