KMP C语言实现

/*  * Description:  *          KMP字符串搜索算法。  * Author  :FinL  * Language: C  * Date    : 2010-09-24  */
#include <stdio.h> #include <string.h> #include <stdlib.h>   static void ComputePrefixFunction(const char *pattern, int *next) {     int i = 0;     int j = -1;       next[0] = -1;     while (i<strlen(pattern)-1)     {         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; }