首页 > 编程学习 > KMP,AC 自动机,以及 fail 树

KMP,AC 自动机,以及 fail 树

发布时间:2022/8/16 22:32:25

开坑待填。

六个月后,yukari1735 准备开始填坑。

全文大概无图!

\(\bold{Border}\)

对于一个字符串 \(s\),若 \(s\) 的一个前缀 \(p\) 同时也是 \(s\) 的后缀且 \(p\neq s\),那么称 \(p\)\(s\) 的一个 \(\text{border}\)

\(\emptyset\) 也是 \(s\)\(\text{border}\)\(|\emptyset|=0\)

记字符串 \(s\)\(\text{border}\) 集合为 \(B(s)\)

\(\bold{Next}\)

对于一个字符串 \(s\)\(\mathrm{next}_i\) 定义为 \(s\)\(i\) 前缀 \(s_{1,i}\) 中的最长 \(\text{border}\) 长度(或结尾下标)。形式化一点就是 \(\mathrm{next}_i=\max\{|x|:x\in B(s_{1,i})\}\)

通过不断地跳 \(\mathrm{next}\) 指针,我们可以遍历 \(s\) 的所有 \(\text{border}\)。因为对于 \(s\) 的两个 \(\text{border}\) \(x,y\ (|x|<|y|)\)\(x\) 也是 \(y\)\(\text{border}\)

所以我们可以得到一个求 \(\mathrm{next}\) 的方法:设当前已经求出了 \(s_{1,i}\)\(\mathrm{next}\),我们直接用上面的方法遍历 \(s_{1,i}\) 的所有 \(\text{border}\),检查是否有 \(\text{border}\) 可以匹配 \(s_{i+1}\)

实际上该算法时间复杂度 \(O(|s|)\)。证明,我也不会 qwq!

\(\bold{Period}\)

\(p\) 为字符串 \(s\) 的一个周期,仅当 \(s_i=s_{i+p}\) 对于所有 \(1\leq i\leq |s|-p\) 都成立。

考虑 \(s\) 的一个 \(\text{border}\) \(x\),其对应着一个长度为 \(|s|-|x|\) 的周期。

同样地,一个周期 \(p\) 也对应着 \(s\) 的一个 \(\text{border}\) \(x=s_{1,|s|-p}\)

也即所有的周期与 \(s\)\(\text{border}\) 存在一一对应的关系,所以我们只需求出 \(B(s)\)

\(\bold{KMP}\)

在主串 \(t\) 中对单个模式串 \(s\) 进行匹配。时间复杂度 \(O(|t|+|s|)\)

首先求出 \(s\)\(\mathrm{next}\),接着从 \(t\) 的起始位置开始匹配,设当前匹配到 \(t_i\)\(s_j\),且当前匹配是合法的,那么下一步尝试匹配 \(t_{i+1}\)\(s_{j+1}\),若成功则 \(i\rightarrow i+1,j\rightarrow j+1\),继续循环。

否则我们遍历 \(s_{1,j}\) 的所有前缀 \(s_{1,k}\),若其也为 \(t_{i-j+1,i}\) 的后缀,则尝试匹配 \(s_{k+1}\)\(t_{i+1}\),由于当前有 \(s_{1,j}=t_{i-j+1,i}\),所以这些前缀 \(s_{1,k}\) 都为 \(s_{1,j}\)\(\text{border}\),用跳 \(\mathrm{next}\) 的方法遍历即可。匹配到后令 \(i\rightarrow i+1,j\rightarrow k+1\),继续循环。

\(j=|s|\) 时,匹配成功。

关于它的时间复杂度为什么线性,我也不会证 qwq!

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号