KMP
MinimumSpanningTree
·
·
算法·理论
\text{KMP} 的原理
时间复杂度：$O(m+n)$。
例如下图所示，要求匹配主串 $s$ 和匹配串 $p$，并求出匹配多少次。
如果采用暴力枚举，时间复杂度 $O(n^2)$，如何优化？
考虑是否能直接跳过中间三次必定失败的匹配。
第一次匹配，发现 $s_8\not=p_8$ 时，观察 $p$ 的前 $7$ 个字符可以发现，$p$ 有前 $3$ 个前缀子串和后 $3$ 个后缀字串完全匹配，可以利用这个性质，直接跳过中间的 $3$ 次无效匹配。
### 前缀函数
我们用 $a$ 数组来表示前缀函数。$a_i$ 表示字符串 $p$ 中前 $i$ 个字符的最大相同前缀和后缀的值。（不包含自身。）
如何高效求前缀函数？
当 $s_{i+1}\not=p_{j+1}$，通过 $j=a_j$ 回跳直到 $s_{i+1}=p_{j+1}$，则 $a_{i+1}=j$。
```cpp
for(int i=1,j=0;i<len2;i++)
{
while(j&&s2[i+1]!=s2[j+1]) j=a[j];
if(s2[i+1]==s2[j+1]) j++;
a[i+1]=j;
}
```
时间复杂度 $O(n)$。
前缀与后缀相等的连续子串又称 $\text{Border}$，简称 $\text{Bd}$。
对于字符串 $S$，记 $mxBd(S)$ 为 $S$ 的最大 $Bd$，$Bd(S)$ 为 $S$ 的 $\text{Bd}$ 集合。上面所讲的前缀函数即为 $\text{mxBd}$。
对于字符串 $S$，若恒有 $S_i=S_{i+p}$，则称 $p$ 为 $S$ 的周期。特殊地，若 $p|n$ 则称为整周期。
$S$ 有长度为 $d$ 的 $\text{Bd}$，等价于 $S$ 有周期 $n−d$。
定理：$Bd(S)=mxBd(S)+Bd(mxBd(S))
证明：显然 \text{Bd} 的 \text{Bd} 是 \text{Bd}；\text{Bd} 是 \text{mxBd} 的 \text{Bd}。这点很好理解，自己在图上画一画就懂了。
\text{KMP} 模板题
P3375 【模板】KMP
有一点需要注意，字符串的下标最好从 1 开始，不然写起来容易错。
首先先求一遍前缀函数，求解方法前文已经讲过，不再赘述。
接下来对两个字符串进行匹配。从 1 开始匹配，如果匹配失败，j 不断通过前缀函数回跳，接下来 s2 的前缀跳到对应 s1 前缀处，就可以跳过中间的无效匹配。当 j 和 s2 的长度相等时，说明匹配成功。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+100;
int len1,len2,a[N];
string s1,s2;
int main()
{
cin>>s1>>s2;
len1=s1.size(),len2=s2.size();
s1=" "+s1,s2=" "+s2;
for(int i=1,j=0;i<len2;i++)
{
while(j&&s2[i+1]!=s2[j+1]) j=a[j];
if(s2[i+1]==s2[j+1]) j++;
a[i+1]=j;
}
for(int i=0,j=0;i<len1;i++)
{
while(j&&s1[i+1]!=s2[j+1]) j=a[j];
if(s1[i+1]==s2[j+1]) j++;
if(j==len2) printf("%d\n",i-len2+2);
}
for(int i=1;i<=len2;i++) printf("%d ",a[i]);
return 0;
}
一些好题+题解
P3435 [POI2006] OKR-Periods of Words 考察对前缀函数的理解。