KMP算法实现

以下为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;
    }
}