以下为KMP代码实现,KMP算法的说明详见算法导论32.4节
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
-
int *ComputePrefixFunc(char *p)
-
{
-
int len = strlen(p);
-
int k=-1, i=1;
-
int *next = (int*)calloc(len, sizeof(int));
-
next[0] = -1;
-
for(i=1; i<len; i++)
-
{
-
while(k>=0 && p[i]!=p[k+1])
-
k = next[k];
-
if(p[k+1]==p[i])
-
k++;
-
next[i] = k;
-
}
-
-
printf("Next:");
-
for(i=0; i<len; i++)
-
{
-
printf(" %d", next[i]);
-
}
-
printf("\n");
-
return next;
-
}
-
-
void KMP_matcher(char *input, char *pattern, int *next)
-
{
-
int slen = strlen(input);
-
int plen = strlen(pattern);
-
int i,j,k;
-
int q=-1;
-
for(i=0; i<slen; i++)
-
{
-
while(q>=0 && pattern[q+1]!=input[i])
-
q = next[q];
-
if(pattern[q+1]==input[i])
-
q++;
-
if(q==plen-1)
-
{
-
printf("Match position: %d\n", i-plen+1);
-
q = next[q];
-
}
-
}
-
}
-
-
int main()
-
{
-
char input[1024];
-
char pattern[1024];
-
int *next = NULL;
-
int i,j,k;
-
while(scanf("%s%s", input, pattern)>0)
-
{
-
next = ComputePrefixFunc(pattern);
-
KMP_matcher(input, pattern, next);
-
free(next);
-
next = NULL;
-
}
-
}
阅读(1994) | 评论(0) | 转发(0) |