多模式匹配与滚动哈希

• fail 指针的语义（指向最长真后缀对应的节点）
• BFS 保证层序（深度递增）构造的性质
• DFS 构造的缺陷（fail 目标未就绪）

AC 自动机的 fail 指针指向"当前节点代表字符串的最长真后缀"所在的节点。构造 fail 时，根节点的子节点 fail 指向根，其余节点的 fail 依赖其父节点的 fail。用 BFS 可以保证按深度递增的顺序处理每个节点，这样处理某个节点时，其父节点的 fail 以及 fail 链上的其他节点都已经构造完毕，可以正确求得 fail。若用 DFS，会沿着一条路径深入到底，此时一些祖先的兄弟节点（本应更早构造）尚未处理，导致 fail 指向的节点尚未完成构造，无法正确建立 fail 指针，甚至产生错误或死循环。

fail 指针的构造具有"自底向上、依赖已构造节点"的特性，BFS 的层序正好满足这种依赖顺序。DFS 破坏了这种顺序，因此必须用 BFS。

• 多项式哈希与模运算
• 碰撞概率的推导（多项式非零根数）
• 双哈希（双模/双底数）的概率乘积

一个长度为 L 的字符串哈希值为 Σ s[i]·B^i mod p，其中 B 是底数、p 是素数模数。两个不同字符串的哈希差是一个次数 ≤ L-1 的非零多项式在某个点（B）处的取值。在模 p 下，非零多项式至多有 L-1 个根，因此当底数 B 在 0..p-1 中随机选取时，碰撞概率 ≤ (L-1)/p ≤ L/p。若使用两个独立的大素数模数（或不同底数）做双哈希，两个哈希同时碰撞的概率为两者的乘积，约为 (L/p1)·(L/p2)，当 p1、p2 都取大素数（如 1e9+7、1e9+9）时，该概率可降到可忽略的级别。

碰撞概率推导基于"多项式在模素数下至多 L-1 个根"这一代数事实，这是随机化底数分析的关键。双哈希利用独立事件概率相乘，把极小的碰撞概率进一步降到实际可忽略，是工程上保证正确性的标准手段。

• Trie 构建（goto 表）
• fail 指针（failure 表）的 BFS 构造
• output 表与命中收集

AC 自动机分三部分：1）goto 表：把所有模式串插入 Trie，每个节点表示一个公共前缀，边表示字符转移；2）failure 表：用 BFS 为每个节点构造 fail 指针，指向其最长真后缀对应的节点，根的子节点 fail 指向根；3）output 表：记录每个节点上命中的模式，并通过 fail 链收集所有等价命中。扫描时，从根出发逐个读文本字符，若当前节点有对应转移则走 goto，否则沿 fail 跳转直到找到转移或到根；每到一个节点都检查 output 表收集命中。复杂度为 O(n+m+z)，其中 n 是文本长度、m 是模式串总长度、z 是命中总数，因为每次 fail 跳转耗散为常数，总跳转次数 O(n)。

AC 的核心是把"所有模式串"合并成一棵 Trie，用 fail 指针避免匹配失败时从头重试。扫描时每个字符最多走一次 goto 加上若干次 fail 跳转，fail 跳转总量摊还为 O(n)，因此总复杂度线性。output 通过 fail 链把隐藏命中也收集到，保证 z 个命中都被输出。

• 二维滚动哈希的两阶段思想
• 每行/每列的哈希前缀
• 降维与 O(1) 查询子矩阵哈希

二维 Rabin-Karp 把"匹配子矩阵"转化为"比较子矩阵的哈希值"。做法是：先对每行计算一维滚动哈希（对每行做多项式哈希，得到哈希前缀），再对列做滚动哈希，把"行哈希组成的新矩阵"再按列滚下来，得到每个矩形区域的二维哈希。具体地，先算每行的前缀哈希 h[i][j] = Σ s[i][k]·B^k（k≤j），然后用这些行哈希对每一列再做一次多项式哈希，得到 H[i][j]，表示以 (0,0) 为左上角、以 (i,j) 为右下角的子矩阵哈希。任意子矩阵的哈希可由 H 的四角 O(1) 组合得到。这样先列后行（或先列行）的两阶段哈希，把二维问题降维为两轮一维滚动哈希，复杂度 O(n·m) 预处理、O(1) 查询任意子矩阵哈希。

关键是"二维多项式哈希"的可分离性：子矩阵哈希可以写成两个方向上独立的多项式组合，从而用二维前缀哈希的四角公式 O(1) 求任意子矩阵。与一维一样，存在碰撞概率，可用双哈希降低。

• 多项式哈希的定义
• 滑动窗口的增量更新公式
• 预计算 p^k 幂次的原因

设子串哈希 H[i..j] = Σ_{t=0}^{j-i} s[i+t]·p^{j-i-t} mod M（p 为底数，M 为模数，即窗口内权重从左到右递减）。滑动一位时，新子串 H[i+1..j+1] 由旧值去掉首位 s[i] 再加上新字符 s[j+1] 得到：先减去 s[i]·p^{j-i}（移除最高位贡献），整体乘以 p（左移一位），再加上 s[j+1]（新位贡献最低位），即 H[i+1..j+1] = ((H[i..j] - s[i]·p^{j-i}) mod M)·p + s[j+1] mod M。其中需要 p^{j-i} 这样的幂次，因此要预计算 p^0, p^1, ..., p^{n-1} mod M 存入数组，否则每次滑动都要快速幂 O(log n) 计算，会破坏 O(1) 滑动的效率。

滚动哈希的"滑动"本质是 O(1) 的增量更新。预计算 p^k 保证 O(1) 取幂，从而滑动窗口内每个子串哈希都能 O(1) 得到，整个算法的额外开销只来自预处理。这是滚动哈希在滑动窗口、子串匹配中高效的原因。

• 坏字符规则与 last occurrence 表的含义
• 跳跃量计算与安全跳跃
• 大规模字符集（Unicode）下的哈希表实现

坏字符表（last occurrence）记录模式串中每个字符最后出现的位置。当匹配到某个位置失配时，设文本字符为 c（坏字符），若 c 在模式串中出现位置为 last[c]，则可将模式串右移使得该 last[c] 与文本的 c 对齐，即移动量 = 失配位置 - last[c]（若 c 不在模式串中，移动量 = 失配位置 + 1，即越过整个模式）。这样把线性扫描变成跳跃式匹配，平均接近 O(n/m)。当字符集是大规模的 Unicode 时，不能开定长数组，而需用哈希表（HashMap 或字典）存储"字符 -> 最后出现位置"，只记录模式串中出现过的字符，空间从 O(|Σ|) 降到 O(m)。

坏字符表是"空间换时间"的典型：用字符的最后位置信息支持安全跳跃。Unicode 字符集下定长数组会爆炸，哈希表只存出现的字符，既省空间又保持 O(1) 平均查询。

• fail 树（fail 边反向成树）的结构
• DFS 序与子树区间映射
• 树状数组维护点权与子树求和

fail 边反向后会形成一棵以根为根的树，称为 fail 树。在 fail 树中，一个节点的祖先（沿 fail 链方向）都代表该节点字符串的后缀，因此"某模式是某扫描状态的后缀"等价于"该模式节点在 fail 树中是扫描状态节点的祖先"。若扫描过程中某个节点被访问，则其所有 fail 祖先都应被计数一次。用 DFS 序把子树映射成连续区间，每个节点在 fail 树上的子树对应一段连续 DFS 区间；当扫描访问到节点 u 时，在 BIT 上 u 的 DFS 位置 +1。这样某模式 p 的出现次数 = 以 p 节点为根的子树区间内所有 +1 之和，用 BIT 的区间求和 O(log n) 查询。在线扫描中，每处理一个字符就更新扫描状态并 +1，可随时查询任意模式的出现次数，无需重新扫描。

关键是把"后缀归属"转化为"fail 树上的祖先关系"，再用 DFS 序 + BIT 把"子树求和"变成"区间求和"。这是把 AC 匹配的动态过程与静态树结构结合，达到在线统计的经典技巧。

• 正串哈希与反串哈希的维护
• O(1) 判回文的思路
• 与 Manacher 的复杂度与正确性取舍

维护正序哈希 h[i]（前缀哈希）与逆序哈希 hr[i]（反串前缀哈希）。任意子串 s[l..r] 的回文判断等价于"该子串的正序哈希等于其逆序子串的哈希"。由于逆序哈希预先算好，任意子串的正序哈希与对应逆序哈希都可 O(1) 求出，两者相等即回文。这样 O(1) 判断任意子串是否回文（预处理 O(n)）。与 Manacher 对比：Manacher 在 O(n) 内求出所有回文半径，且无碰撞、确定性高；双向哈希 O(1) 判回文灵活，可结合二分/DP 求最长回文子串（O(n log n)），但有哈希碰撞风险（需双哈希）。取舍：需要所有回文半径用 Manacher（更稳、O(n)）；只需零散 O(1) 判回文或配合二分时，双向哈希编程更简单。

双向哈希把"回文"这个结构性质转化为"字符串相等"的哈希比较，从而 O(1) 得出。Manacher 用中心扩展+对称性避免比较，确定性更高但代码更复杂。二者是"哈希近似"与"精确"的取舍。

• next 数组与字符集无关
• 坏字符表依赖字符集大小
• 两种表的构建与适用边界

KMP 的 next 数组只依赖模式串自身的结构（最长公共前后缀），与字符集大小完全无关，构建时只需 O(m) 时间、O(m) 空间，与字符集是多少个字符无关。Boyer-Moore 的坏字符表需要为每个可能出现的字符记录最后位置，若用定长数组则空间为 O(|Σ|)（依赖字符集大小），在 Unicode 等大字符集下需要哈希表。因此 KMP 的 next 数组在"空间与构建稳定性"上不依赖字符集，更稳定；而 BM 的坏字符表在字符集大时需额外处理（哈希表），且其跳跃效率高度依赖字符集特征（ASCII 英文文本效果好）。

next 数组的"稳定性"源于它只编码模式串内部的结构关系，而不是对外部字符集抽样。选型时，若字符集大或输入不可预测，KMP 更稳定；若字符集小且文本随机，BM 跳跃更快。

• 坏字符与好后缀规则的跳跃机制
• 随机文本下的平均跳跃量
• 最坏情况分析与上界

BM 从模式串末尾向前匹配，失配时用坏字符规则和好后缀规则取较大者作为跳跃量。在英文/随机文本中，模式串末尾字符在文本中出现的概率低，坏字符规则通常能跳过很大一段（约 m 个字符），因此平均每次跳跃量大，总比较次数约 O(n/m)。但最坏情况（如模式串和文本都由几乎相同的字符组成）下，坏字符规则和好后缀规则都无法有效跳跃，需回到 O(n) 次比较，加上可能的重叠检查，最坏仍为 O(n+m)。BM 的复杂度上界是 O(n+m)，这是在所有输入上的最坏保证。

平均达到 O(n/m) 是因为随机文本中"末端字符"很难匹配，从而跳跃量大；最坏 O(n+m) 是算法保证的确定性上界。实践中最常使用 BM 的变体（如 Boyer-Moore-Horspool），以坏字符规则为主。

• 各算法的时间/空间复杂度
• 模式集规模与共享前缀的利用
• 位并行与正则的适用条件

模式集小时（几十个），可用 KMP 逐个匹配或简单正则，构建开销低。模式集大（成百上千到百万）且共享前缀多时，用 AC 自动机，一次扫描文本即可命中所有模式，复杂度 O(n+总长度+z)，但内存随模式总长度增长（可用稀疏表/双数组优化）。Shift-And 位并行适合模式长度较短（通常 ≤ 64/128，受机器字长限制），用位掩码在一次字符转移中同时匹配多个模式，速度快但模式长度受限。正则引擎适合模式本身是复杂规则（通配、分组）而非简单固定串，但大字典下正则构建与匹配都可能慢。选型原则：固定串+大规模→AC；短模式+大量→位并行；复杂规则→正则；小规模→KMP。

选型是"模式数、模式长度、模式复杂度、字符集"四维权衡。AC 用共享前缀压缩结构，位并行用字长并行度，正则用表达力，KMP 用简单性，各自边界清晰。

• 完整 goto 表 next[N][S] 的空间爆炸
• 稀疏表（邻接表/哈希）
• 双数组 Trie（Double-Array）与动态分配

完整 goto 表用二维数组 next[N][S]（N 个节点、S 个字符），每个字符都占一个 int，当字符集 S 很大（如 Unicode 的 6 万+）时空间 O(N·S) 会爆炸。优化方案：1）稀疏表：每节点只存实际存在的转移（用邻接表或哈希表），空间 O(N·平均出度)，但查询稍慢；2）双数组 Trie：用 base 和 check 两个数组实现，通过 base 索引 + 字符偏移定位，空间接近 O(N) 且查询 O(1)，是竞赛与生产常用的紧凑方案；3）动态分配：按需分配每个节点的子节点数组，避免为每个字符都分配空间。这些方法在保持匹配功能的同时大幅压缩内存。

空间爆炸的根源是"二维数组为每个字符都预留空间"。稀疏/双数组/动态分配都只存实际用到的转移，空间从 O(N·S) 降到 O(N·σ)，其中 σ 是实际出度（平均远小于 S）。

• 哈希碰撞的误报问题
• 二次验证（精确比较）的时机
• 多模式候选过滤框架

Rabin-Karp 用哈希快速排除大部分不匹配位置，但哈希相等不代表一定匹配（碰撞误报），因此当哈希相等时需做一次精确的逐字符比较（二次验证）来确认。单模式场景：哈希相等则 O(m) 精确比对；多模式场景采用"哈希候选过滤+精确比对"框架：把所有模式串的哈希放入一个哈希集合（或按哈希分桶），扫描文本时对每个位置的子串哈希在集合中查找，若命中则取对应模式做精确比对确认，从而避免对每个模式都做完整匹配。这样误报只增加少量精确比较开销，整体仍接近 O(n+总长度)。

哈希是"过滤"而非"证明"：它把候选大幅缩小，最后的正确性由精确比对保证。双哈希可进一步减少误报，但不能完全消除，精确比对是最终保险。

• 固定底数/模数下构造碰撞的原理
• 生日攻击与碰撞概率
• 随机化底数与双哈希的防御

若底数 B 和模数 p 固定且公开，攻击者可以构造两个不同的字符串使它们的多项式哈希相等（通过求解多项式方程或利用模 p 下的代数关系），从而制造碰撞。生日攻击利用"约 √p 个哈希值中就有较大概率出现两个相同"这一现象，在哈希值空间有限时降低碰撞难度。防御手段：1）随机化底数：每次运行时随机选一个底数 B（运行前随机），攻击者无法预知底数，难以构造碰撞；2）双哈希：用两个不同的大素数模数（或多组参数）计算，攻击者需同时构造两个哈希都相等的串，难度大幅上升。两者结合可把碰撞概率降到可忽略且抗构造攻击。

固定参数的可预测性使攻击者能离线构造碰撞。随机化底数把"确定性碰撞"变成"概率性碰撞"，双哈希把该概率进一步乘积化，从而抵御生日攻击与构造攻击。

• AC 自动机对通配符的退化原因
• FFT 卷积匹配的原理
• 位并行（Shift-And）处理通配符

AC 自动机基于 Trie 的确定性字符转移，通配符 ? 表示位置可匹配任意字符，使得 Trie 的转移变为"任意字符"的多分支，节点的 goto 无法线性描述，最坏时每个字符都要尝试所有可能，导致退化（甚至指数级）。替代方案：1）FFT 卷积：把字符映射为数值，把"匹配"编码为"对应位置乘积求和"，用 FFT 求卷积，在 O(n log n) 检验所有对齐位置，支持通配符（通配符位置置 0 或特殊处理）；2）位并行（Shift-And）：用位掩码表示每个字符的匹配位，通配符位对所有字符都置 1，一次位运算即可滑动匹配，支持 ? 通配符且长度受字长限制。两者都能处理通配符，避免 AC 的退化。

AC 的确定性结构依赖"明确字符"，通配符打破这种确定性。FFT 用卷积把"匹配检测"转化为全局数值运算，位并行用位向量表达通配符的任意性，是两种有效的替代。

• 各算法的优势与最坏情况
• 多模式与流式场景的扩展
• 选型权衡

单模式精确匹配：KMP 最坏 O(n+m) 稳定，适合对抗性输入；Boyer-Moore 在英文/随机文本平均快（O(n/m)），适合文本长、字符集小；Rabin-Karp 平均 O(n+m)，但最坏因碰撞变 O(n·m)，适合配合滚动哈希做多模式/子串统计。多模式：KMP/BM 不适用（需逐个匹配），应升级为 AC 自动机（基于 KMP 思想）或对 Rabin-Karp 做哈希集合过滤。流式场景：KMP 的 next 数组可做确定性自动机（每字符 O(1)），适合流式；AC 也可流式（状态持久化）；Rabin-Karp 需前缀信息，流式需维护窗口哈希；BM 从末尾匹配，不适合在线流式。

单模式高频用 KMP/BM，多模式用 AC/Rabin-Karp 集合，流式用 KMP/AC 的自动机形态。选型取决于"模式数、是否已知全文、是否对抗输入"。

• AC 自动机在敏感词过滤中的应用
• 内存占用评估与优化
• 模式库动态更新的策略

敏感词过滤中，把所有敏感词构建成 AC 自动机，一次扫描文本即可命中所有敏感词，复杂度 O(n+总长度+z)。工程部署需考虑：1）内存占用：完整 goto 表在敏感词多、字符集大时爆炸，需用双数组 Trie 或稀疏表压缩；2）构建时机：模式库频繁更新时，每次全量重建代价高，可采用"增量更新"（新词插入现有 fail 结构）或"双缓冲"（后台重建新自动机，切换原子化，避免服务中断）；3）模式库卸载：定期从数据库/配置中心加载，构建后原子替换。还需处理大小写、变形、分隔符等变体，可先归一化再匹配。

敏感词过滤是 AC 的典型大规模应用。内存优化与"构建-切换"策略是工程落地的关键，按需更新可避免全量重建的停顿。

• 负数取模的溢出错误
• 未预计算 p^k 的复杂度退化
• 漏掉长度信息导致的误判

常见误区及影响：1）负数取模：Java 中负数取模仍为负，导致哈希值错误，需先加 MOD 再取模（(x % MOD + MOD) % MOD）；2）未预计算 p^k：每次 O(log n) 快速幂，滑动哈希退化为 O(log n) 每个子串，总复杂度上涨；3）比较时漏掉长度信息：不同长度的子串哈希若算法未含长度归一化，可能误判相等，需比较哈希时同时保证长度相同（或哈希定义含长度）；4）双哈希共用模数：两套哈希若模数相同（或底数成比例），碰撞事件不再独立，乘积概率失效，防御效果大打折扣；5）溢出：大数相乘溢出 int 需用 long 或取模。

这些误区都源于实现的细节与"哈希应唯一、独立、稳定"的要求。正确处理取模、幂次、长度与独立性，才能保证滚动哈希正确高效。

• AC 流式处理的当前状态持久化
• 分块读入时的边界处理
• 增量匹配的正确性

流式场景下，文本按块读入，AC 自动机只需持久化"当前扫描状态"（当前所在节点），每读入一个字符更新状态并收集 output，即可无缝衔接下一块，无需重新扫描。边界问题在于：模式串可能跨块边界（模式串的一部分在块尾、一部分在块头），若只在本块内匹配会漏掉跨块模式。解决方法是保留块尾的"重叠区"（长度 = 最长模式长度 - 1），把这块与下一块开头拼接后重新匹配，或维护状态+窗口缓冲，确保跨块匹配正确。由于 AC 状态本身就是增量信息，配合窗口缓冲即可正确流式处理。

AC 的"当前状态"是完整的增量信息，天然支持流式。跨块边界是唯一需要处理的地方，用重叠缓冲或恰当的窗口管理即可保证不漏匹配。

• output 与 fail 链的关系
• 逐层收集的退化（最坏深度）
• 字典后缀链接的优化

在 AC 自动机中，一个节点可能命中多个模式（当前节点是某个模式，其 fail 链上的祖先也可能是模式）。若每到一个节点都沿 fail 链逐层向上收集所有命中，最坏情况下 fail 链长度可达 O(m)（模式串总长），导致扫描退化到 O(n·m)。优化：预计算"字典后缀链接"（dictionary suffix link），对每个节点只记录"fail 链上最近的、本身是模式终结的节点"（即下一个能命中的 fail 祖先）。这样收集命中时只需跟着字典后缀链接一步步跳，只访问真正有命中的节点，总收集次数 = 命中数 z，从而保证 O(n+z) 的收集开销。

逐层收集的浪费在于访问大量"无命中"的 fail 节点。字典后缀链接跳过这些节点，只保留"有命中"的跳转，把收集复杂度和命中数 z 绑定，避免退化。

• KMP 自动机（补全 next 为确定性转移表）
• O(n) 流式扫描、每字符只处理一次
• 与 AC 自动机的关系（单模式特例）

KMP 自动机把 next 数组补全成"确定性转移表"：对每个状态 j 和每个字符 c，定义转移 nextState[j][c] = 匹配到前缀长度 j 时读入字符 c 后应跳到的状态（若 c 匹配则 j+1，否则沿 fail 链跳到能匹配的状态）。这样构造后，扫描时每读一个字符只需查一次转移表，O(1) 更新状态，无需 while 循环回溯，每字符只处理一次，实现 O(n) 流式扫描。AC 自动机本质上是这一思想的多模式推广：把多个模式的 next 数组合并成 Trie，补全成转移表（用 fail 指针），扫描时每字符 O(1) 转移。因此 KMP 自动机可视为 AC 自动机在单模式下的特例。

补全转移表把"失配时的动态回退"静态化为"预计算的确定性转移"，牺牲空间（O(m·Σ)）换取 O(n) 流式。AC 是多模式共享 Trie 的同类推广。