KMP算法-C语言版

void getNext(int * next,char *s )
{
    int j=0;
    next[0]=0;
    for(int i=1;i<strlen(s);i++)
    {
        while(j>0 && s[i]!=s[j] )
        {
            j=next[j-1];
        }
        if(s[i]==s[j])
            j++;

        next[i]=j;
    }
}

int KMP(char * haystack,char * needle)
{
    int len1=strlen(haystack);
    int len2=strlen(needle);

    if(len2==0) return 0;
    int *next=malloc(sizeof(int)*len2);
    getNext(next,needle);

    int j=0;
    for(int i=0;i<len1;i++)
    {
        while(j>0&&haystack[i]!=needle[j])
        {
            j=next[j-1];
        }
        if(haystack[i]==needle[j])
            j++;
        if(j==len2) return i-len2+1;
    }
    return -1;

}