用KMP算法实现字符串匹配

KMP是一种非常快的字符串匹配算法，其思想的核心在于主串的i不回退，子串的j回退到next[j],在这时候就又引进了一个求next数组的问题，而KMP算法的重点也就是求next数组；而朴素查找算法的核心是主串的i一定要回退。
KMP算法与BF（朴素查找算法）相比，时间复杂度提升了很多其中BF算法的时间复杂度为O(N*M)，而KMP算法的时间复杂度为O(N+M).

下面用代码示例说明KMP算法：

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
//KMP算法
//先得到next数组
static int *GetNext(const char *sub)
{
int lensub=strlen(sub);

    assert(lensub>=2);
int *next=(int*)malloc(lensub * sizeof(int));
next[0]=-1;
next[1]=0;


int i=2;
int k=0;
while(i<lensub)
    {
if(sub[k]==sub[i-1] || k==-1)
 {
next[i++] = ++k;
        }
else
        {
            k=next[k];
        }
    }
return next;
}



int KMP(const char *str,const char *sub,int pos)
{
int lens=strlen(str);
int lensub=strlen(sub);
if(pos<0 || pos >=lens)
    {
return -1;
    }
int i=pos;
int j=0;

//创建next数组存取j回退的位置k的值,其大小与sub相同
 //int *next=(int *)malloc(lensub * sizeof(int));
int *next=GetNext(sub);
    assert(next != NULL);

while(i<lens && j <lensub)
    {
if(j==-1 || str[i]==sub[j])
 {
            i++;
            j++;
        }
else
        {
            j=next[j];//i不回退，j回退到k的位置，即next数组
        }
    }

    free(next);

if(j >= lensub)
    {
return i-j;
    }
else
    {
return -1;
    }
}




int main()
{
    char *str="ababcabcdabcde";
    char *sub="abcd";
printf("%d\n",KMP(str,sub,3));
printf("%d\n",KMP(str,sub,6));
printf("%d\n",KMP(str,sub,10));
return 0;
}

打印结果为：
5
9
-1