KMP 算法
KMP 算法是一种改进的字符串匹配算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度 O(m+n)O(m+n)O(m+n)。
朴素做法
你有两个串 ababbaba、aba，求第二个串在第一个串中出现了多少次。
设两串的长度分别为 n,mn,mn,m，则时间复杂度 O(nm)O(nm)O(nm)。
我们看到，标 ☆ 的几步可以优化。那应该怎么优化呢？
next 数组
我们发现，当一个串匹配失败时，不总是需要再次从头开始匹配。如果这个串有公共的前后缀，那么可以节约时间。
那我们就在这方面下点功夫。设 next[x]next[x]next[x] 表示这个串前 xxx 位的公共的前后缀的最大长度，且 next[x]<xnext[x]<xnext[x]<x，x∈[1,len]x\in[1,len]x∈[1,len]，lenlenlen 表示这个串的长度。
以下为求 nextnextnext 数组的步骤。
定义两个指针 i=2,j=0i=2,j=0i=2,j=0。
因为 str[i]≠str[j+1]str[i]\neq str[j+1]str[i]̸=str[j+1]，且 j=0j=0j=0，所以 next[i]=next[2]=0next[i]=next[2]=0next[i]=next[2]=0。
因为 str[i]=str[j+1]str[i]=str[j+1]str[i]=str[j+1]，匹配成功。所以将 jjj 指针右移一位，next[i]=j+1next[i]=j+1next[i]=j+1。
匹配成功，jjj 右移一位。
匹配失败，令 j=next[j]j=next[j]j=next[j]，继续判定。
仍然无法配对。因此 next[i]=0next[i]=0next[i]=0。
luogu P3375
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
int next[1000010];
char str1[1000010],str2[1000010];
int len1,len2,t=0;
int main(){
memset(next,0,sizeof(next));
scanf("%s%s",str1+1,str2+1);
len1=strlen(str1+1);len2=strlen(str2+1);
for(reg int i=2;i<=len2;++i){
while(t>0&&str2[t+1]!=str2[i]) t=next[t];
if(str2[t+1]==str2[i]) ++t;
next[i]=t;
}
t=0;
for(reg int i=1;i<=len1;++i){
while(t>0&&str2[t+1]!=str1[i])t=next[t];
if(str2[t+1]==str1[i]) ++t;
if(t==len2) printf("%d\n",i-t+1);
}
for(reg int i=1;i<=len2;++i)
printf("%d ",next[i]);
}
loj 10043
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
char str[1010],s[1010];
int next[1010];
int t=0,l,len;
int ans;
int main(){
do{
scanf("%s",str+1);
if(str[1]=='#'&&str[2]=='\0') break;
scanf("%s",s+1);
l=strlen(str+1);len=strlen(s+1);
memset(next,0,sizeof(next));
t=ans=0;
for(int i=2;i<=len;++i){
while(t>0&&s[t+1]!=s[i]) t=next[t];
if(s[t+1]==s[i]) ++t;
next[i]=t;
}
t=0;
for(int i=1;i<=l;++i){
while(t>0&&s[t+1]!=str[i]) t=next[t];
if(s[t+1]==str[i]) ++t;
if(t==len) ++ans,t=0;
}
printf("%d\n",ans);
}while(1);
}
