KMP算法分析
KMP算法D.E.Knuth, V.R.Pratt和J.H.Morris三个人提出的，所以叫KMP算法。
求next原始函数。
void get_next(char *T, int next[])
{
int i=1;
next[i]=0;
int j=0;
while(i<(strlen(T)))
{
if(j==0||T[i]==T[j]) {++i; ++j; next[i]=j}
else
j=next[j];
}
}
匹配函数
int Index_KMP(char *s , char *t, int pos)
{
int i=pos;
int j=1;
while(i<=strlen(s)&&j<=strlen(t))
{
if(j==0|| s[i]==t[j]) {i++; j++}
else j = next[j];
}
if(j>strlen(t)) return (i-strlen(t)); //matched
else return 0; // not match
}
改进的匹配算法
void get_nextval(char *t, int next[])
{
int i=1;
nextval[1]=0;
int j=0;
while(i
{
if(j==0||t[i]=t[j])
{
++i; ++j;
if(t[i] != t[j]) nextval[i]=j;
else nextval[i] = nextval[j];
}
else j=nextval[j];
}
}
阅读(1230) | 评论(0) | 转发(0) |
