我不喜欢阅读长篇的还夹杂着数学公式的逻辑分析，所以看到很多讲解KMP算法的资料，觉得挺伤脑筋的，但花了挺长时间尝试学习KMP算法，KMP算法的思路是明白了，但是编程实现它可能还有点晕，参考了一些资料，它们的next数组有几种版本，有些是从下标0开始，有的是从下标1开始。

   一、我的尝试版

   现在有一个子串t="aabacaaabaabba"

   当在t[0]处匹配失败时，下一次匹配还是从0开始匹配，所以next[0]=0.

   当在t[1]处匹配失败时，t[1]的前缀只有一个a,所以下一次匹配还是从下标0处开始，因而next[1]=0。

   当在t[2]处匹配失败时，t[2]的前缀有一对元素匹配，所以下一次匹配从下标1处开始，因而next[2]=1。

   当在t[3]处匹配失败时，t[3]的前缀没有对称元素，所以下一次匹配从下标0处开始，因而next[3]=0。

   当在t[4]处匹配失败时，t[4]的前缀有一对元素对称，所以下一次匹配从下标1处开始，因而

next[4]=1。

   当在t[5]处匹配失败时，t[5]的前缀没有元素对称，所以下一次匹配从下标0处开始，因而

next[5]=0。

   当在t[6]处匹配失败时，t[6]的前缀有一对元素对称，所以下一次匹配从下标1处开始，因而

next[6]=1。

   当在t[7]处匹配失败时，t[4]的前缀有两对元素对称，所以下一次匹配从下标2处开始，因而

next[7]=2。

   同理，我们可以分析出后面的next元素。

   next数组填充元素过程我们知道了，但是还只是停留在理论上，真正地编程实现算法还需要更多考虑。下面是结合我自己的想法实现的求next数组的算法。

void get_next(char *t, char *next){    int i, j;    int tlen = strlen(t);    i = 1;    j = 0;    next[0] = 0;    next[1] = 0;    while(i < tlen)    {        if(t[i] == t[j])        {            i++;    j++;            next[i] = j;        }        else{            if(j == 0)            {                i++;                next[i] = j;            }            j = next[j];        }    }}

   循环执行的次数与子串的长度和字符重复情况有关系，时间复杂度为O(n)。

   匹配算法如下：

int get_index(char *s, char *t, int pos){    char *next;    int slen, tlen, i, j;    slen = strlen(s);    tlen = strlen(t);    next = (char*)malloc(sizeof(tlen)+1);    get_next(t, next);    i = pos;    j = 0;    while(i < slen && j < tlen)    {        if(s[i] == t[j] )        {            i++;   j++;        }        else{            if(j==0)                i++;            j = next[j];        }    }    if(j >= tlen)        return (i-tlen);    else        return 0;}

   时间复杂度为O(n+m)。

   二、教科书版

   我们数据结构课程时，用的课本是清华大学出版社出版，严蔚敏和吴伟民编写的数据及结构（C语言版），真心没搞懂分析过程。

   求next数组算法：

void get_nextval(char *t, int nextval){    i= 0;    nextval[1] = 0;    j = 0;    while(i < t[0])    {        if(j ==0 || t[i] == t[j])        {            i++;    j++;            if(t[i] != t[j])                nextval[i] = j;            else                nextval[i] = nextval[j];        }        else            j = nextval[j];    }}

   那本书上给出了两个求next数组的算法，不过get_nextval更优。t[0]存放的是t串的字符个数。下面的s串的s[0]的字符个数。

   模式匹配算法：

int index_KMP(char *s, char *t, int pos){    i = pos;    j = 1;    while(i <= s[0] && j <= t[0])    {        if(j == 0 && s[i] == t[j])        {            i++;    j++;        }        else            j = next[j];    }                                                                                    if(j > t[0])        return i = t[0];    else        return 0;}

   三、一个模式匹配程序

#include
     
      #include
      
       #include
       
        void get_next(char *t, char *next){    int i, j; int count = 0;    int tlen = strlen(t);    i = 1;    j = 0;    next[0] = 0;    next[1] = 0;    while(i < tlen)    {        count++;        if(t[i] == t[j])        {            i++;            j++;            next[i] = j;        }        else{            if(j == 0)            {                i++;                next[i] = j;            }            j = next[j];        }    }    next[tlen] = '\0';    printf("count:%d\n", count);}int get_position(char *s, char *t, int pos){    char *next;    int slen, tlen, i, j;    slen = strlen(s);    tlen = strlen(t);    next = (char*)malloc(sizeof(tlen)+1);    get_next(t, next);    i = 0;    j = 0;    while(i < tlen)    {        printf("next[%d] = %d\n", i, next[i]);        i++;    }     i = pos;    while(i < slen && j < tlen)    {        if(s[i] == t[j] )        {            i++;            j++;        }        else{            if(j==0)                i++;            j = next[j];        }    }    if(j >= tlen)        return (i-tlen);    else        return 0;}void main(){    char *s = "aaabaaaaaaaabbbababacbacbab";    char *t =  "aabacaaabaabba";    int pos, index;      index = get_position(s, t, pos);    printf("index: %d\n", pos);}