KMP算法学习体会
这个算法数据结构课上老师讲过，当时大致听懂了，一直没写过，今天抽个时间复习了一下。以下是一点体会。
给定两串S,T,判断串T是否与S中的一个字串匹配，S为主串,T为模式串.KMP算法可以在O(m+n)时间内实现串的匹配,其中m,n分别为两串的长度。
判断两个串是否配，就是把主串与模式串中的字符一一比较，若当前的字符匹配则在比后面的。关键是当前不匹配模串T该如何移动，如果从头开始比较当然可以，但这样效率很低，KMP算法中有一个next数组,来解决这个问题，当串T中j不匹配时，只需j回到next[j]即可。
附代码：
void KMP()
{
int i=0,j=0;
len1=strlen(S);
len2=strlen(T);
while(i<len1&&j<len2)
{
if(S[i]==T[j])
{
i++;j++;
}
else if(j==0)
i++;
else
j=next[j];
}
if(j>=len2)
cout<<i-len2<<endl;
}
next数组如后缀数组中的Height数组一样使KMP算法具有强大的功能,而且可以巧妙的解决单个串中的一些问题。网上看了很多next的定义，觉的这个容易懂。即当一个字符以0为起始下标时，next[i]表示不为自身的最大首尾重复字串的长度。也就是说从模式串T[0...i-1]的第一个字符开始取一段长度为m(m<i-1)的字串，再取模式串T[0...i-1]的后m个字符作字串如果两个字串相同，则该串就是一个首尾重复字串，就是要找出最大的m值。要注意条件“是不为自身”。next的计算也已很巧妙,但比较难懂, 要认真思考。方法是用next[0],next[1],..next[i]求出next[i+1],如果T[next[i]]=T[i],则可以得到next[i+1]=next[i]+1;否则我们要在前面找适当的next值满足T[next[k]]=T[i]，因为我们通过next[i]已无法的到next[i+1],但可以从前面的满足条件的next值上加1,
具体实现:
void CalNext()
{
int i=0,j=-1;next[0]=-1;
while(i<T.size())
{
if(j==-1||T[i]==T[j])
{
i++;j++;
next[i]=j; //满足条件next值在前基础上加1
}
else
j=next[j]; //此时向前回溯，寻找满足条件的next值
}
}
附PKU 2406和PKU 1961解题报告
如果能清楚的理解KMP算法中next的真正含义，就可以很轻松的解决了，当时用后缀数组DC2算法解2406超时了，不会DC3。求连续重复字串，next数组中不是以重复字串定义的吗，只需判断连续即可。对数组中最后一个字符， k=next[length]表示后面的移动length-k个后第k个就会与最后一字符length-1对应相等，而且前面所有的都对应相等，因为要满足 next[length]的性质，这里要注意的是，如果这里next[length]=0时，要回溯在前面找k值，最后判断length是其整数倍即可，因为next数组中k时最大值，那么length-k就是最小值。
附代码：
附代码：
Source Code
Problem: 2406 User: zhouxc
Memory: 5320K Time: 110MS
Language: G++ Result: Accepted
#include "stdio.h"
#include "string.h"
int len,next[1000001];
char T[1000005];
void CalNext()
{
int i=0,j=-1;next[0]=-1;
while(i<=len)
{
if(j==-1||T[i]==T[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
while(scanf("%s",T)&&T[0]!='.')
{
len=strlen(T);
CalNext();
int t=next[len];
while(t!=-1)
{
int L=len-t;
if(len%L==0)
{
printf("%d/n",len/L);
break;
}
else
t=next[t];
}
}
return 0;
}
Problem: 1961 User: zhouxc
Memory: 5320K Time: 500MS
Language: G++ Result: Accepted
#include "stdio.h"
#include "string.h"
int len,next[1000001];
char T[1000001];
void CalNext()
{
int i=0,j=-1;next[0]=-1;
while(i<=len)
{
if(j==-1||T[i]==T[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
int test=1;
while(scanf("%d",&len)&&len!=0)
{
scanf("%s",T);
CalNext();
printf("Test case #%d/n",test++);
for(int i=2;i<=len;i++)
if(i%(i-next[i])==0&&next[i])
printf("%d %d/n",i,i/(i-next[i]));
printf("/n");
}
return 0;
}