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;

}
End

本文标题:KMP算法-C语言版

本文链接:http://chisato.cn/index.php/archives/189/

除非另有说明,本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

声明:转载请注明文章来源。

最后修改:2022 年 03 月 18 日 05 : 13 PM
如果觉得我的文章对你有用,请随意赞赏