kmp字符串查找算法

好几次都遇到字符串查找的题目，说实话，第一次遇到kmp，确实是搞懂了，但是做得少，老是会忘怎么写，即使知道原理，不会写就是不会吧，今天把它记录下来。

//优化过后的next 数组求法

void GetNextval(char* p, int next[])

{

int pLen = strlen(p);

next[0] = -1;

int k = -1;

int j = 0;

while (j

{

//p[k]表示前缀，p[j]表示后缀

if (k == -1 || p[j] == p[k])

{

++j;

++k;

//较之前next数组求法，改动在下面4行

if (p[j] != p[k])

next[j] = k; //之前只有这一行

else

//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]

next[j] = next[k];

}

else

{

k = next[k];

}

}

}

int main()

{

int i,j;

while(~scanf("%s",str)&&str[0]!='#')

{

scanf("%s",s);

lens = strlen(s);

kmp();

int sum = 0;

j = 0;

i = 0;

while(str[i])

{

if(j==-1||str[i]==s[j])

{

++i;

++j;

}

else

{

j = _next[j];

}

if(j==lens)

{

// 匹配成功位置开始为j-i;

++sum;

j=0;

}

}

printf("%d\n",sum);

}

return 0;

}

不求上进的咸鱼