KMP 算法

摘要

用于字符串匹配,在 O(n) 复杂度内完成匹配。

算法思想

对于朴素算法,当 即匹配失败时,是将整个 S 向后移动一位,复杂度 O(mn)。这种算法的缺点在于,移动一位时会重复比较已比较的位置。

KMP 算法的想法是:设法利用已知信息,不要把”搜索位置”移回已经比较过的位置,而是继续把它向后移。

那么问题来了,究竟应该移多少位呢?
试想 S=ABCDABD ,T=ABCDCABCABCABD,比较情况如下:
-表示成功匹配,^表示不匹配

ABCDABCDABDABD
ABCDABD
------^

可见ABCDAB是成功匹配。而第 7 位(1 起点)不匹配。如果直接移到第 8 位,则错过了第 5 位开始的匹配串。而将位于第 1 位的匹配串移动到第 5 位,理由是: ,同时 也是 的后缀,也是 S[1~6] 的前缀。

对于 S[i], 定义 表示最大的 使得 的后缀,也就是最长的

对于 S=ABCDABD,next[] 如下:

S     A B C D A B D
next 0 0 0 0 1 2 0

Next 的求法

next 的求法与 KMP 算法本身相似,思想是自己匹配自己。

假设我们已知 的值,求 .

此时定义 .根据 可判断 的匹配情况:

  • 如果 , 则 ;
  • 否则,将 赋值为 ,继续循环比较,直到

模板

LuoguP3375【模板】KMP字符串匹配

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;

char s1[N],s2[N];

void getnext(char *s,int * nex,int ls){//1 起点
nex[1]=0;// 第一位失配
for(int i=2,j=0;i<=ls;i++){
while(j&&s[i]!=s[j+1])j=nex[j];
if(s[i]==s[j+1])++j;
nex[i]=j;
}
}
int nex[N];
void kmp(char *s,int ls,char *t,int lt){
getnext(s,nex,ls);
for(int i=1,j=0;i<=lt;i++){
while(j>0&&t[i]!=s[j+1])j=nex[j];
if(t[i]==s[j+1])++j;
if(j==ls)printf("%d\n",i-ls+1),j=nex[j];
}
}
int main(){
scanf("%s%s",s1+1,s2+1);
int l1=strlen(s1+1),l2=strlen(s2+1);
kmp(s2,l2,s1,l1);
for(int i=1;i<=l2;i++)printf("%d ",nex[i]);
return 0;
}

Border

对一个串,其相等的前后缀是一组border。而我们KMP算法其实就是在求,即 表示的是 的最长的border。

循环串(周期)

对于一个长度为 的字符串 ,若存在一个前缀 满足 循环构成,且最后一个循环节是 的前缀(即最后的尾部不一定是完整的 ),那么称 是循环串,其循环节为 .显然一个循环串可能有多个循环节。如果尾部循环节是完整的 ,那么 就是严格循环串。

对于一个循环串,其循环节与border是一一对应的。如图:

p1

那么判断一个串是否存在严格循环的循环节,用next指针判断 即可,这个结合border就能证明

border的树形结构

在KMP中的border结合next指针,呈现一个树形的结构

p2

那么KMP显然可以求border。利用树上倍增或者二分,可以对前缀a求<=b的最长border