KMP C语言实现

/*

 * Description:

 *          KMP字符串搜索算法。

 * Author  :FinL

 * Language: C

 * Date    : 2010-09-24

 */

#include

#include

#include

 

static void ComputePrefixFunction(const char *pattern, int *next)

{

    int i = 0;

    int j = -1;

 

    next[0] = -1;

    while (i

    {

        if (-1 == j || pattern[i] == pattern[j])

        {

            ++i;

            ++j;

            next[i] = j;    

        }

        else

            j = next[j];

    }

}

char * KmpMatch(const char *target, const char *pattern)

{

    int i = 0,j=0;

    int targetlen,patternlen;

    int *next = NULL;

    

    targetlen = strlen(target);

    patternlen = strlen(pattern);

 

    next = (int *)malloc(patternlen * sizeof(int));

    if (NULL == next)

        return NULL;

 

    ComputePrefixFunction(pattern, next);

 

    while (i < targetlen && j < patternlen)

    {

        if (-1 == j || target[i] == pattern[j])

        {

            ++i;

            ++j;

        }

        else

            j = next[j];

    }

    free(next);

    next = NULL;

 

    if (j >= patternlen)

        return (char *)&target[i - patternlen];

    else

        return NULL;

}

 

int main()

{

    char *target = "abababaababacb";

    char *pattern = "ababacb";

    char *p = NULL;

 

    printf("Target    : %s\nPattern : %s\n", target, pattern);

    p = KmpMatch(target, pattern);

    if (p)

        printf("Pattern found at position : %d\n", p - target + 1);

    else

        printf("Pattern not found!\n");

return 0;

}