c语言kmp算法

kmp是一种可以在字符串中迅速找到某一个指定的连续字串的算法。
要理解这个算法首先要了解如何得到字串的next值。

传统的匹配方法中，每与字串进行一次未完全匹配的比较，都要从头开始再进行一次，于是kmp就有next数组来避免这种重复的比较，进而降低时间复杂度。

next数组的含义：与字串相对应的下标表示的数的意义是一直到该字符的后缀与前缀相同的字符个数。

求next数组：

void getNext(char T[],int n)
{
    int l,k;
    next[0]=0;
    k=0;
    for(l=1; l<n; l++)
    {
        while(k>0&&T[l]!=T[k])
            k=next[k-1];
        if(T[l]==T[k])
            k++;
        next[l]=k;
    }
}

接下来就是利用next数组求是否匹配了：

已经匹配的字符不需要再退回去重新从头开始比较。

void kmpMatch(char *s,int sLength,char *p,int pLength,int *next)
{
    int pPoint=0;
    for(int i=0; i<=sLength-pLength; i++)
    {
        while(pPoint!=0&&(s[i]!=p[pPoint]))
            pPoint=next[pPoint-1];
        if(s[i]==p[pPoint])
        {
            pPoint++;
            if(pPoint == pLength)
            {
                printf("找到:%d \n",i-pPoint+1);
=                pPoint=next[pPoint-1];
            }
        }
    }
}