**KMP算法总结
相关介绍KMP算法的文章很多,在这里并不累述,主要写一下其中的要点
KMP算法主要是两个步骤
getnext : 生成next表(时间复杂度O(lenP))
next[i] 表示下标范围 0~i 的P(pattern)字符串的最长公共前缀后缀的长度。
2.kmp: 字符串匹配(时间复杂度O(lenT))
在T(target)串中匹配P(pattern)串
这两个部分代码完全相似。
#include<stdio.h>
#include<string.h>
int main()
{
//getnext:生成next表(前缀后缀的最大overlap长度)
int next[999];
char T[]="aabbbcbabbbaabbaaa",P[]="abba";
int lenT=strlen(T),lenP=strlen(P);
next[0]=0;
next[-1]=0;
for(int i=1;i<lenP;i++)
{
int j=next[i-1];
while(P[j]!=P[i] && j!=0) j=next[j-1];
next[i]=(P[j]==P[i])? j+1 : 0;
}
//kmp:在T(target)串中匹配P(pattern)串
int j=0;
for(int i=0;i<lenT;i++)
{
while(P[j]!=T[i] && j!=0) j=next[j-1];
if(P[j]==T[i]) j++;
if(j==lenP) printf("%d\n",i-lenP+1);
}
return 0;
}
生成next表是用自己递推自己的方式实现的,大致思想就是每次能不能接到目标位置后面,若能则结果是这个位置匹配数量+1;否则结果就是0个公共前缀后缀;
字符串匹配大致思想是当每次失配时,就沿着next表找到新的匹配点,这样避免了无用的比较。
注意:
1、循环节
当前缀后缀串有重叠时,错开的那一部分的长度如果能整除字符串的长度,那么错开的这一部分便是字符串的一个循环节。
2、匹配次数
每次匹配过后还要继续匹配,注意可能会有匹配串overlap,所以更新的匹配长度为next[j-1](详见下面最后一个例题)
KMP算法例题
POJ 2752 公共前缀-后缀串(用kmp的next表)
#include<stdio.h>
#include<string.h>
char s[400005];
int next[400005];
int len;
void getnext()
{
next[-1]=0;next[0]=0;
for(int i=1;i<len;i++)
{
int j=next[i-1];
while(s[j]!=s[i] && j>0) j=next[j-1];
next[i] = (s[j]==s[i])? j+1:0;
}
}
void print(int t)
{
if(next[t]>0)
{
print(next[t]-1);
printf("%d ",next[t]);
}
}
int main()
{
while(scanf("%s",s)>0)
{
len=strlen(s);
getnext();
print(len-1);
printf("%d\n",len);
}
return 0;
}
LA3026循环节(用kmp的next表)
注意怎么判断循环节!
#include<stdio.h>
#include<string.h>
char s[1000005];
int next[1000005];
void getnext(int len)
{
//生成next表(前缀后缀的最大overlap长度)
next[0]=0;
next[-1]=0;
for(int i=1;i<len;i++)
{
int j=next[i-1];
while(s[j]!=s[i] && j!=0) j=next[j-1];
next[i]=(s[j]==s[i])? j+1 : 0;
}
}
int main()
{
int n,t=1;
scanf("%d",&n);
while(n!=0)
{
printf("Test case #%d\n",t++);
scanf("%s",s);
int len=strlen(s);
getnext(len);
for(int i=2;i<=len;i++)
if(next[i-1]>0 && (i%(i-next[i-1]))==0) printf("%d %d\n",i,i/(i-next[i-1])); //判断循环节
printf("\n");
scanf("%d",&n);
}
return 0;
}
POJ 2406 (用kmp的next表)
#include<stdio.h>
#include<string.h>
char s[1000005];
int next[1000005];
void getnext()
{
//生成next表(前缀后缀的最大overlap长度)
int len=strlen(s);
next[0]=0;
next[-1]=0;
for(int i=1;i<len;i++)
{
int j=next[i-1];
while(s[j]!=s[i] && j!=0) j=next[j-1];
next[i]=(s[j]==s[i])? j+1 : 0;
}
}
int main()
{
scanf("%s",s);
while(s[0]!='.')
{
int ans=1;
int len=strlen(s);
getnext();
if((len%(len-next[len-1]))==0) ans=len/(len-next[len-1]);
printf("%d\n",ans);
scanf("%s",s);
}
return 0;
}
POJ 3461 字符串匹配次数(kmp)
每次匹配过后还要继续匹配,注意可能会有匹配串overlap,所以更新的匹配长度为next[j-1]
#include<stdio.h>
#include<string.h>
char P[10005],T[1000005];
int next[10005];
int sum;
void kmp()
{
//生成next表(前缀后缀的最大overlap长度)
int lenT=strlen(T),lenP=strlen(P);
next[0]=0;
next[-1]=0;
for(int i=1;i<lenP;i++)
{
int j=next[i-1];
while(P[j]!=P[i] && j!=0) j=next[j-1];
next[i]=(P[j]==P[i])? j+1 : 0;
}
//在T(target)串中匹配P(pattern)串
int j=0;
for(int i=0;i<lenT;i++)
{
while(P[j]!=T[i] && j!=0) j=next[j-1];
if(P[j]==T[i]) j++;
if(j==lenP)
{
sum++;
j=next[j-1]; //字符串匹配计数时要这样修改!代表我下一次匹配之前已经匹配了next[j-1]位了
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(;n>0;n--)
{
sum=0;
scanf("%s",P);
scanf("%s",T);
kmp();
printf("%d\n",sum);
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章