参考:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://blog.csdn.net/v_july_v/article/details/7041827
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://blog.csdn.net/v_july_v/article/details/7041827
-
#include <stdio.h>
-
#include <string.h>
-
-
void GetNext(char* p,int next[])
-
{
-
int pLen = strlen(p);
-
next[0] = -1;
-
int k = -1;
-
int j = 0;
-
while (j < pLen - 1)
-
{
-
printf("j=%i\tk=%i\t",j,k);
-
printf("%c\t",p[j]);
-
printf("%c\n",p[k]);
-
-
if (k == -1 || p[j] == p[k])
-
{
-
++k;
-
++j;
-
next[j] = k;
-
}
-
else
-
{
-
k = next[k];
-
}
-
}
-
-
-
printf("---------------------\n");
-
int i;
-
for (i=0;i<pLen;i++){
-
printf("next[%i]:%i\n",i,next[i]);
-
}
-
}
-
int KmpSearch(char* s, char* p)
-
{
-
int i = 0;
-
int j = 0;
-
int sLen = strlen(s);
-
int pLen = strlen(p);
-
int next[pLen];
-
GetNext(p,next);
-
while (i < sLen && j < pLen)
-
{
-
if (j == -1 || s[i] == p[j])
-
{
-
i++;
-
j++;
-
}
-
else
-
{
-
j = next[j];
-
}
-
}
-
if (j == pLen)
-
return i - j;
-
else
-
return -1;
-
}
-
-
-
void main(){
-
char* s="acabaabaabcacaabc";
-
char* p="abaabc";
-
int i=KmpSearch(s,p);
-
printf("=====================\n");
-
printf("%s\n",s);
-
printf("%s\n",p);
-
printf("%i\n",i);
- }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29254281/viewspace-1791038/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
在组合中找到重复的数据
下一篇：
两种丢失更新
请登录后发表评论
登录
全部评论
