KMP
_Cheems
·
·
个人记录
前言
不会画图 QwQ，有些图需要放大，请见谅。
前置知识
border
定义：在字符串 S 中，若有长度为 k 的前缀与长度为 k 的后缀相等，则称该前缀（后缀）为 S 的 1 个 \operatorname{border}。
一个简单性质：字符串 S 的 \operatorname{border} 的 \operatorname{border} 也是 S 的 \operatorname{border}。
证明：
KMP 算法
算法介绍
用于快速查找字符串 T 在 S 中的匹配位置。
先谈谈无优化的暴力解法，时间复杂度为 O(|S|*|T|)。
而 KMP 可视作暴力算法的优化，但其时间复杂度仅有 O(|S|+|T|)。
它是怎么优化的呢？假设我们要在 abcabcabf 中匹配 abcabf。
回想暴力的流程，首先枚举点 i，然后依次判断 S_{i+j-1} 是否等于 T_j。实际上，这部分与 KMP 是大致相同的。
不过，KMP 枚举 i、维护 j。代表 T_1 ~ T_j 与 S_{i-j+1} ~ S_i 一一对应。
若 S 与 T 的对应位不同（称为失配），暴力算法则退出循环，将 i 前进一位，但 KMP 则考虑运用已知条件，找到最优继续匹配位置。
定义失配数组 nxt[j] 表示 T 长度为 j 的前缀的最长 \operatorname{border}（的结尾指针）。
发生失配时，可以通过改变 j 的值使得 S_i=T_{j+1}。 因为 T_1 ~ T_{nxt[j]} = T_{j-nxt[j]+1} ~ T_j，所以令 j=nxt[j]，这样既保证正确性又达到优化的效果。
$i=6$、$j=5$ 时，发生失配：
（为啥我列表没了诶！）
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| a | b | c | a | b | c | a | b | f |
| 1 | 2 | 3 | 4 | 5 | | | |
| a | b | c | a | b | | | |
$nxt[4]=2$，将 $j$ 改为 $2$：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |-----------: |
| a | b | c | a | b | c |a |b | f |
| | | | 1 | 2 | | | |
| | | | a | b | | | |
继续匹配，直到 $i=9$、$j=6$，$T$ 已被遍历完，于是匹配
位置为 $4$：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |-----------: |
| a | b | c | a | b | c |a |b | f |
| | | | 1 | 2 | 3 | 4 | 5 | 6 |
| | | | a | b | c | a | b | f |
算法结束。
#### 失配数组的建立
可粗略理解为 $T$ 的自匹配，同样记录 $i$、$j$。
假设我们已经知道 $nxt_1$ ~ $nxt_{i-1}$ 的值，而 $j=nxt_{i-1}$，接下来怎么推出 $nxt_i$？
从定义入手，$nxt_{i-1}$ 告诉我们：$T_1$ ~ $T_j$ $=$ $T_{(i-1)-j+1}$ ~ $T_{i-1}$。
代数角度较难理解，画图就很清晰了：
显然，只要绿色格子相同，即满足 $T_{j+1} = T_i$时，$nxt_i=j+1
假如不相同呢？为了方便表达，定义 z=nxt_j。
由 \operatorname{border} 的性质可知，T_1 ~ T_z 也是 T_1 ~ T_{i-1} 的前缀的 \operatorname{border}，用图来表示就是这样：
显然，满足 T_{z+1} = T_i 即可。
以此类推，底层原理就是如此。
代码实现时，我们不需要 z 等变量，不断令 j=nxt_j 即可。
代码模板
裸题
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define sc scanf
#define pr printf
using namespace std;
const int N=1e6+5;
int nxt[N],len1,len2;
char st1[N],st2[N];
void border()
{
int j=0;
nxt[1]=0;
for(int i=2; i<=len2;i++) //注意从2开始枚举
{
while(j&&st2[j+1]^st2[i])
{
j=nxt[j];
}
if(st2[j+1]==st2[i])
{
++j;
}
nxt[i]=j;
}
}
void kmp()
{
int j=0;
for(int i=1; i<=len1;i++)
{
while(j&&st1[i]^st2[j+1])
{
j=nxt[j];
}
if(st1[i]==st2[j+1])
{
++j;
}
if(j==len2)
{
pr("%d\n",i-len2+1);
j=nxt[j]; //为了继续匹配
}
}
}
int main()
{
sc("%s%s",st1+1,st2+1);
len1=strlen(st1+1);
len2=strlen(st2+1);
border();
kmp();
for(int i=1; i<=len2;i++)
{
pr("%d ",nxt[i]);
}
return 0;
}
时间复杂度分析
先讨论 KMP 主函数的最坏时间复杂度。
首先，i 总共增加 |S| 次，j 只会随 i 增加而增加，所以 j 至多增加 |S| 次。
在最坏情况下，如 S=\{aaaa...\} 时，nxt_j=j-1，同时 j≥0。结合上述条件，可知 j 至多减少 |S| 次。
于是，主函数的时间复杂度是 O(|S|)；同理，预处理部分的时间复杂度是 O(|T|)。所以总时间复杂度就是 O(|S|+|T|)。
失配树
失配树模板
如上面这题，当题目是求两前缀的最长公共 \operatorname{border} 长度时怎么办？直接枚举会超时，这时失配树就出场了。
利用 \operatorname{border} 的性质，我们发现 S 的 \operatorname{border} 集合可表示为 S 的最大 \operatorname{border} 与其 \operatorname{border} 集合。
因此，S 的 \operatorname{border} 集合就是 nxt_{|S|} 、nxt_{nxt_{|S|}}、nxt_{nxt_{nxt_{|S|}}}...... 诶，很像是树中父子节点的关系。
于是，对于每个点 i，建立一条由 nxt_i 指向 i 的边，所建成的树称作失配树。
失配树中，对于任意点 u，它的所有祖先节点就是它的所有 \operatorname{border}。
回顾题目，易发现两前缀的最长公共 \operatorname{border} ，就是失配树上两结点的 LCA，本题解决。