引言
kmp相关算法主要用于解决字符串的匹配问题，本文除了探讨最基础的kmp算法，还会介绍扩展kmp算法，注意本文主要写给作者看，很多基础的东西都没有讲，写得也相对比较随意
kmp相关算法
一、kmp算法
1、原理
kmp最核心的思想就是充分利用已知信息，这样就可以避免不必要的重复检查。
具体地，我们考虑模式串与匹配串之间的关系，假设模式串
s
2
s2
s2当前匹配到第
i
i
i位(即将匹配)，匹配串
s
1
s1
s1当前匹配到第
j
j
j位，如果
s
1
[
j
]
=
s
2
[
i
]
s1[j]=s2[i]
s1[j]=s2[i]，那么显然
i
+
+
,
j
+
+
i++,j++
i++,j++，不过如果
s
1
[
j
]
≠
s
2
[
i
]
s1[j]\ne s2[i]
s1[j]=s2[i]，按照暴力算法的思路，我们会让
j
−
=
i
−
2
j-=i-2
j−=i−2，同时令
i
=
1
i=1
i=1，然后接着下一轮的匹配。但kmp算法对此作出了改进，由于我们已知
s
1
[
j
−
i
+
1
∼
j
−
1
]
s1[j-i+1\sim j-1]
s1[j−i+1∼j−1]与
s
2
[
1
∼
i
−
1
]
s2[1\sim i-1]
s2[1∼i−1]是完全相同的，因此我们已经知道了
s
1
s1
s1的一部分信息，那么其实就有办法不让
j
j
j改变，啥意思呢，也就是我们可以
O
(
1
)
O(1)
O(1)找到一个最大的
k
k
k满足
k
<
i
k<i
k<i并且
s
1
[
j
−
k
∼
j
−
1
]
s1[j-k\sim j-1]
s1[j−k∼j−1]与
s
2
[
1
∼
k
]
s2[1\sim k]
s2[1∼k]完全相同，这样的话
j
j
j就不会改变了，此时我们已经排除了一定不合理的匹配方案，直接进入到第一个合理的匹配情形，然后再检查是否满足
s
1
[
j
]
=
s
2
[
k
]
s1[j]=s2[k]
s1[j]=s2[k]即可，并且由于
i
i
i每次最多加
1
1
1，其实总体就能够做到线性时间复杂度。
那么怎么找这个 k k k就很关键，也是算法的核心，考虑设 n x t [ i ] nxt[i] nxt[i]表示模式串 s 2 s2 s2的第 i i i位对应的要求的答案。本质上来说就是求解 s 2 s2 s2的长度为 i i i的前缀的最长相同真前缀和真后缀。因此不妨让模式串自己与自己匹配即可，这个部分需要好好理解一下，原因不太好说明，有一点dp的味道吧。
零基础入门移步：这里。
2、代码
这里以LuoGu P3375 【模板】KMP字符串匹配为例给出一份代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int nxt[maxn];
char s1[maxn],s2[maxn];
int main(){
scanf("%s%s",s1+1,s2+1);
int n=strlen(s1+1),m=strlen(s2+1);
int j=0;
for(int i=2;i<=m;++i){//自己与自己匹配求nxt数组
while(j && s2[j+1]!=s2[i])j=nxt[j];
if(s2[j+1]==s2[i])j++;
nxt[i]=j;
}
j=0;
for(int i=1;i<=n;++i){
while(j && s2[j+1]!=s1[i])j=nxt[j];
if(s2[j+1]==s1[i])j++;
if(j==m){
printf("%d\n",i-m+1);
j=nxt[j];
}
}
for(int i=1;i<=m;++i)printf("%d ",nxt[i]);puts("");
}
3、习题
例题一
题目来源：POJPower Strings
题面：
题解：本题考查对
n
x
t
nxt
nxt数组的理解，假设串长为
l
e
n
len
len，则
n
x
t
[
l
e
n
]
nxt[len]
nxt[len]代表最长公共前后缀，对于一个周期重复串
a
b
c
d
a
b
c
d
a
b
c
d
.
.
.
a
b
c
d
abcdabcdabcd...abcd
abcdabcdabcd...abcd而言，不难发现它的
l
e
n
−
n
x
t
[
l
e
n
]
len-nxt[len]
len−nxt[len]其实就是最小重复片段，对应的
n
n
n自然也是最大的，如果
(
l
e
n
−
n
x
t
[
l
e
n
]
)
∤
l
e
n
(len-nxt[len])\nmid len
(len−nxt[len])∤len那么其实该串的最小重复片段其实就是串本身，对应的
n
=
1
n=1
n=1。
代码：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1000005;
char s[maxn];
int nxt[maxn];
int main(){
while(~scanf("%s",s+1)){
if(s[1]=='.')break;
int len=strlen(s+1);
nxt[1]=0;
int j=0;
for(int i=2;i<=len;++i){
while(j&&s[1+j]!=s[i])j=nxt[j];
if(s[1+j]==s[i])j++;
nxt[i]=j;
}
int le=len-nxt[len];
if(len%le==0)printf("%d\n",len/le);else printf("1\n");
}
}
例题二
题目来源：POJPeriod
题面：
题解：跟上题一样，就当练习罢了。
代码：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1000005;
char s[maxn];
int nxt[maxn];
int main(){
int kase=0;
int n;
while(scanf("%d",&n) &&n){
scanf("%s",s+1);
int j=0;
printf("Test case #%d\n",++kase);
for(int i=2;i<=n;++i){
while(j && s[1+j]!=s[i])j=nxt[j];
if(s[1+j]==s[i])j++;
nxt[i]=j;
if(i%(i-nxt[i])==0 && i!=i-nxt[i])printf("%d %d\n",i,i/(i-nxt[i]));
}
puts("");
}
}
二、扩展kmp算法
1、原理
顾名思义，就是一种类似kmp的算法，用于求解
s
s
s串的每个后缀与
t
t
t串的最长公共前缀，也就是
l
c
p
lcp
lcp，后面我们用
e
x
t
e
n
d
[
i
]
extend[i]
extend[i]数组表示。
在算法中同样设置一个
n
x
t
nxt
nxt数组，不过在这个算法中，
n
x
t
[
i
]
nxt[i]
nxt[i]是针对
t
t
t串而言的，代表
t
t
t串的以字符
t
[
i
]
t[i]
t[i]开头的后缀和
t
t
t串自身的
l
c
p
lcp
lcp。
假设我们已经求出了 n x t [ ] nxt[] nxt[]数组，那么如何求出 e x t e n d [ ] extend[] extend[]数组呢，我们枚举 i i i从 1 1 1到 l e n s len_s lens，设 n o w now now是满足 n o w + e x t e n d [ n o w ] − 1 now+extend[now]-1 now+extend[now]−1最大在 s s s串中的位置，如果 i + n x t [ i − n o w + 1 ] − 1 < n o w + e x t e n d [ n o w ] − 1 i+nxt[i-now+1]-1<now+extend[now]-1 i+nxt[i−now+1]−1<now+extend[now]−1，容易发现此时有 e x t e n d [ i ] = n x t [ i − n o w + 1 ] extend[i]=nxt[i-now+1] extend[i]=nxt[i−now+1]，否则的话一定有 e x t e n d [ i ] ≥ n o w + e x t e n d [ n o w ] − i extend[i]\ge now+extend[now]-i extend[i]≥now+extend[now]−i，令 c u r = n o w + e x t e n d [ n o w ] − i cur=now+extend[now]-i cur=now+extend[now]−i，我们可以从 c u r cur cur处开始匹配 s s s和 t t t串，也就是从 s [ i + c u r ] s[i+cur] s[i+cur]与 t [ 1 + c u r ] t[1+cur] t[1+cur]开始往后比，直到字符不等为止，此时还要更新 n o w now now才行。
至于怎么求 n x t [ ] nxt[] nxt[]数组，我们类比kmp算法容易发现只需要让 t t t串自己与自己作一次exkmp即可。
如果看不懂上面的原理(其实上面只是复述了一下算法)，可以看这里
2、代码
这里以LuoGu P5410 【模板】扩展 KMP（Z 函数）为例给出一份参考代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e7+5;
typedef long long ll;
char a[maxn],b[maxn];
int nxt[maxn],extend[maxn];
void init_excmp(char *s,int len){
nxt[1]=len;
if(len==1)return;
int cur=0;
while(2+cur<=len && s[1+cur]==s[2+cur])cur++;
nxt[2]=cur;
int now=2;
for(int i=3;i<=len;++i){
if(i+nxt[i-now+1]<now+nxt[now])nxt[i]=nxt[i-now+1];
else{
cur=max(now+nxt[now]-i,0);
while(i+cur<=len && s[i+cur]==s[1+cur])cur++;
now=i;
nxt[i]=cur;
}
}
}
void excmp(char *s,int lens,char *t,int lent){
int now=1,cur=0;
while(now+cur<=min(lens,lent) && s[now+cur]==t[now+cur])cur++;
extend[now]=cur;
for(int i=2;i<=lens;++i){
if(i+nxt[i-now+1]<now+extend[now])extend[i]=nxt[i-now+1];
else{
cur=max(now+extend[now]-i,0);
while(i+cur<=lens && 1+cur<=lent && s[i+cur]==t[1+cur])cur++;
extend[i]=cur;
now=i;
}
}
}
int main(){
scanf("%s%s",a+1,b+1);
int lena=strlen(a+1),lenb=strlen(b+1);
init_excmp(b,lenb);
excmp(a,lena,b,lenb);
ll ans1=0,ans2=0;
for(int i=1;i<=lenb;++i){
ans1^=1ll*i*(nxt[i]+1);
}
for(int i=1;i<=lena;++i){
ans2^=1ll*i*(extend[i]+1);
}
printf("%lld\n%lld\n",ans1,ans2);
}
3、习题
例题一
题目来源：CFB. Password
题面：
题解：本题让求解一个最长串满足既是前缀又是后缀还是中间的某个子串(即不是前缀也不是后缀)。这道题根据扩展kmp的特点做即可，如果理解了原理不是很难做出本题。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
char s[maxn];
int nxt[maxn];
void init(char *s,int len){
int now=2,cur=0;
nxt[1]=len;
if(len==1)return;
while(s[2+cur]==s[1+cur])cur++;
nxt[now]=cur;
for(int i=3;i<=len;++i){
if(i+nxt[i-now+1]<now+nxt[now])nxt[i]=nxt[i-now+1];
else{
cur=max(0,now+nxt[now]-i);
while(i+cur<=len && s[i+cur]==s[1+cur])cur++;
nxt[i]=cur;
now=i;
}
}
}
int vis[maxn];
int main(){
scanf("%s",s+1);
int len;
init(s,len=strlen(s+1));
int ans=0,mx=0;
for(int i=2;i<=len;++i){
mx=max(mx,nxt[i]);
if(nxt[i]!=len-i+1)vis[nxt[i]]=1;
if(nxt[i]==len-i+1 && (vis[nxt[i]] || nxt[i]<mx)){
ans=max(ans,nxt[i]);
}
}
if(ans){
for(int i=1;i<=ans;++i)printf("%c",s[i]);puts("");
}else printf("Just a legend\n");
}
例题二
题目来源：UVA#455 Periodic Strings
题面：
题解：本题是让求最短的一个重复串，其实跟kmp非常像，我们可以枚举
i
i
i从小到大
(
2
∼
l
e
n
)
(2\sim len)
(2∼len)遍历
n
x
t
[
i
]
nxt[i]
nxt[i]数组，找到第一个满足
n
x
t
[
i
]
+
i
−
1
=
=
l
e
n
nxt[i]+i-1==len
nxt[i]+i−1==len并且
(
i
−
1
)
∣
l
e
n
(i-1)\mid len
(i−1)∣len的位置，那么
i
−
1
i-1
i−1就是答案，如果找不到的话答案就是
l
e
n
len
len。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
char s[maxn];
int nxt[maxn];
void init(char *s,int len){
nxt[1]=len;
if(len==1)return;
int now=2,cur=0;
while(2+cur<=len && s[1+cur]==s[2+cur])cur++;
nxt[now]=cur;
for(int i=3;i<=len;++i){
if(i+nxt[i-now+1]<now+nxt[now])nxt[i]=nxt[i-now+1];
else{
cur=max(now+nxt[now]-i,0);
while(i+cur<=len && s[i+cur]==s[1+cur])cur++;
nxt[i]=cur;
now=i;
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s+1);
int len;
init(s,len=strlen(s+1));
int ans=len;
for(int i=2;i<=len;++i){
if(i+nxt[i]-1==len && len%(i-1)==0){
ans=i-1;
break;
}
}
printf("%d\n",ans);
if(t)puts("");
}
}
例题三
题目来源：UVA#11022 String Factoring
题面：
题解：本题考虑区间dp，设
d
p
[
l
]
[
r
]
dp[l][r]
dp[l][r]表示
s
[
l
∼
r
]
s[l\sim r]
s[l∼r]压缩后的最小字符数，那么考虑转移有
d
p
[
l
]
[
r
]
=
m
i
n
1
≤
k
<
r
{
d
p
[
l
]
[
k
]
+
d
p
[
k
+
1
]
[
r
]
}
dp[l][r]=min_{1\le k<r}\{dp[l][k]+dp[k+1][r]\}
dp[l][r]=min1≤k<r{dp[l][k]+dp[k+1][r]}，除此之外还可以将
s
[
l
∼
r
]
s[l\sim r]
s[l∼r]单独表示为一个重复周期串的形式，也就是要写一个
c
a
l
(
l
,
r
)
cal(l,r)
cal(l,r)函数，具体来说可以用扩展kmp实现(kmp其实也行)。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
char s[maxn];
int nxt[maxn],dp[maxn][maxn];
int cal(char *s,int len,int l,int r){
int now=2,cur=0;
if(len==1)return 1;
nxt[1]=len;
while(2+cur<=len && s[1+cur]==s[2+cur])cur++;
nxt[now]=cur;
for(int i=3;i<=len;++i){
if(i+nxt[i-now+1]<now+nxt[now])nxt[i]=nxt[i-now+1];
else{
cur=max(now+nxt[now]-i,0);
while(i+cur<=len && s[i+cur]==s[1+cur])cur++;
nxt[i]=cur;
now=i;
}
}
for(int i=2;i<=len;++i){
if(i+nxt[i]-1==len && len%(i-1)==0){
return dp[l][l+i-2];
}
}
return len;
}
int main(){
while(scanf("%s",s+1)){
if(s[1]=='*')break;
int n=strlen(s+1);
for(int i=1;i<=n;++i)dp[i][i]=1;
for(int len=2;len<=n;++len){
for(int i=1;i<=n-len+1;++i){
int j=i+len-1;
dp[i][j]=cal(s+i-1,len,i,j);
for(int k=i;k<j;++k){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
printf("%d\n",dp[1][n]);
}
}
例题四
题目来源：UVA#11475 Extend to Palindrome
题面：
题解：本题就是让求最长后缀回文串。设原串
s
s
s反转后为
s
′
s'
s′，构造新串t=s’+’$’+s，然后求一下扩展kmp，然后再t串的dollar符之后去寻找最大的nxt,并且要求i+nxt[i]-1=lent，也就是找到一个在s串中最长的后缀回文串。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
char s[maxn],ss[maxn];
int nxt[maxn];
void init(char *s,int len){
int now=2,cur=0;
nxt[1]=len;
while(2+cur<=len && s[1+cur]==s[2+cur])cur++;
nxt[now]=cur;
for(int i=3;i<=len;++i){
if(i+nxt[i-now+1]<now+nxt[now])nxt[i]=nxt[i-now+1];
else{
cur=max(now+nxt[now]-i,0);
while(i+cur<=len && s[1+cur]==s[i+cur])cur++;
nxt[i]=cur;
now=i;
}
}
}
int main(){
while(~scanf("%s",s+1)){
int len=strlen(s+1);
int n=0;
for(int i=len;i>=1;--i){
ss[++n]=s[i];
}
ss[++n]='$';
for(int i=1;i<=len;++i){
ss[++n]=s[i];
}
ss[n+1]='\0';
init(ss,n);
int ans=0;
for(int i=len+2;i<=n;++i){
if(i+nxt[i]-1==n){
ans=nxt[i];
break;
}
}
int nn=len;
for(int i=len-ans;i>=1;--i){
s[++nn]=s[i];
}
s[nn+1]='\0';
printf("%s\n",s+1);
}
}
例题五
题目来源：CF432D Prefixes and Suffixes
题面：
题解：板子题。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
char s[maxn];
int cnt[maxn],vis[maxn],nxt[maxn];
void init(char *s,int len){
int now=2,cur=0;
nxt[1]=len;
if(len==1)return;
while(2+cur<=len && s[1+cur]==s[2+cur])cur++;
nxt[now]=cur;
for(int i=3;i<=len;++i){
if(i+nxt[i-now+1]<now+nxt[now])nxt[i]=nxt[i-now+1];
else{
cur=max(now+nxt[now]-i,0);
while(i+cur<=len && s[i+cur]==s[1+cur])cur++;
nxt[i]=cur;
now=i;
}
}
}
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
init(s,len);
int ans=0;
for(int i=1;i<=len;++i){
cnt[nxt[i]]++;
if(i+nxt[i]-1==len)vis[nxt[i]]=1,ans++;
}
for(int i=len;i>=1;--i){
cnt[i]+=cnt[i+1];
}
printf("%d\n",ans);
for(int i=1;i<=len;++i){
if(vis[i]){
printf("%d %d\n",i,cnt[i]);
}
}
}