KMP
KMP 是一种字符串单模匹配算法，复杂度 \(\operatorname{O(n+k)}\) 。
KMP 这个名字的由来：它是三个人：D.E · Knuth 、J.H · Morris 和 V.R · Pratt 同时发现的。
其中， \(n\) 是主串的长度， \(k\) 是模式串的长度。由于至少要遍历主串和模式串的每个字符，此类算法的最佳复杂度是 \(\operatorname{O(n+k)}\) ，KMP 差不多达到了此类算法能达到的最佳时间复杂度。
模板题（AcWing.831）
题目描述
给定一个字符串 \(s\)，以及一个模式串 \(p\)，所有字符串中只包含大小写英文字母以及阿拉伯数字。求出模式串 \(p\) 在字符串 \(s\) 中所有出现的位置的起始下标。
- 模式串 \(p\) 在字符串 \(s\) 中多次作为子串出现。
样例
in：
3
aba
5
ababa
out：
0 2
KMP 实现
思路
首先想想暴力。
用 \(flag\) 表示是否匹配。先设 \(flag=1\) ， 再用 \(i\) 枚举起始位置， \(j\) 枚举模式串的每个字符下标，如果有不匹配的，则 \(flag=0\) 。
for(ll i=1;i<=n;i++)
{
bool flag=1;
for(ll j=1;j<=m;j++)
if(s[i]!=p[j]){flag=0;break;}
}
接下来要把它优化。
暴力匹配算法在每个字符失配后都回溯到了 \(i+1\) 的位置，显然这会浪费很多时间。
如果我们找到模式串中两个相同的字串，每次匹配就可以从前一个子串
这样一来就可以做到只回溯 \(j\) 。（这里读者自己画图理解，这里很关键）
下图演绎了 KMP 如何匹配主串和模式串（原创图）。
动态演示：
注：如果用 #include <bits/stdc++.h> ，那就不能用 next 做数组名，我在这里用的是 nxt 。
匹配代码
for(ll i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=p[j+1]) j=nxt[j];
if(s[i]==p[j+1]) j++;
if(j==n){write(i-n),putchar(' '),j=nxt[j];}
}
那怎么知道 \(j\) 回溯到哪去呢？
可以预处理出一个 \(next\) 数组，用来维护每个 \(j\) 回溯的位置。
下图演绎了如何预处理出 \(next\) 数组。
预处理代码
inline void init()
{
for(ll i=2,j=0;i<=n;i++)
{
while(j&&p[i]!=p[j+1]) j=nxt[j];
if(p[i]==p[j+1]) j++;
nxt[i]=j;
}
}
代码
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return (f==1)?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}//卡常
ll n=read(),m,nxt[N];
char p[N],s[N];
inline void init()
{
for(rll i=2,j=0;i<=n;i++)
{
while(j&&p[i]!=p[j+1]) j=nxt[j];
if(p[i]==p[j+1]) j++;
nxt[i]=j;
}
}//初始化next数组
int main()
{
scanf("%s",p+1);m=read();scanf("%s",s+1);
init();
for(rll i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=p[j+1]) j=nxt[j];
if(s[i]==p[j+1]) j++;
if(j==n){write(i-n),putchar(' '),j=nxt[j];}
}
return 0;
}