对KMP算法中next数组的深入理解（这个算法真有点难懂）

void  Next(SString  T)
{
   int  next[1024];//即表示next数组中最多存有1024个数字
   int  j=1;//从模式串的第1位起
   int  k=0;//当k=0时，表示主串的i，向后移一位
   next[1]=0;//初始化，当模式串第一位就与主串失配时，主串直接后移一位
   while(j<T.length)
   {//T.length实际上比模式串T的实际长度要大一，因为我从一开始进行存储
   if(k==0||T.base[j]==T.base[k])
      {
        k++;
        j++;
        next[j]=k;
       }    
    else
    {
    k=next[k];//当模式串第k位与第j位失配时，k=next[k]，此时必定存在，因为很明显，k比j至少要少一位。
    }
   }//这个while循环没看懂没关系，这是这个算法的精髓所在，下面会深入讨论


 }
那么上面的while循环到底是什么意思呢？实际上，kmp算法其实就是在主串与模式串失配是，在模式串中，找到最大的相同前缀和后缀。怎样找呢？ 将模式串看成既是主串又是自己的模式串，

实际上，严蔚敏老师的书上已经说的很清楚了，用递归的思想来求，定义next[1]=0，我们假设next[j]=k,也就是说，第j位失配时，用第k位来进行匹配。那么第j+1位呢？有两种情况，一是当j=k时，显然，next[j+1]=k+1,二是当j!=k时，next[j+1]=next[k]+1。 看到这里不知道大家明白了没有，实际上，上面的while就是可以将这个递归的意思表达出来，至于while中为什么要加k==0,现在应该很清楚了吧，既然是递归，你必须要有一个初始条件吧，类比于数学归纳法。

**如果像上面那么说，还没懂的话，可以看看这段代码来源于这个博客

 1 void makeNext(const char P[],int next[])
 2 {
 3     int q,k;//q:模版字符串下标；k:最大前后缀长度
 4     int m = strlen(P);//模版字符串长度
 5     next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
 6     for (q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
 7     {
 8         while(k > 0 && P[q] != P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k
 9             k = next[k-1];      
10         if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
11         {
12             k++;
13         }
14         next[q] = k;
15     }
16 }


将next数组理解了之后，就很容易理解KMP算法本身了。

Status   Make_Kmp(SString  S, SString  T,int &e)//主串与模式串相互比较，并返回相同字符时在主串中的第一个字符位置
{
    Next(T);
    int  i = 1;
    int  j = 1;
    while (i < S.length&&j < T.length)
    {
        if (j==0||S.base[i] == T.base[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
        if (j>= T.length)
        {
            e = i - T.length+1;
            printf("\r\n%d,%d\r\n", i, T.length);
            printf("从第%d个位置开始匹配", e);
        }
        if (i >= S.length)
        {
            printf("主串中，没有该字符串");
        }
    }
    return  0;
}


这里j==0，可以有两种理解，一是kmp算法的特性，二是用了next数组。

KMP算法总代码
// s0722(2).cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "string.h"
#include "stdlib.h"
#define  MAXLENG  100
#define  INCREMENT   10
typedef  int   Status;
typedef  char   ElemType;
//求next数组,即满足关系next[j]=k时，模式串使用第k个字符与主串进行匹配
typedef  struct  SString
{
    ElemType  *base;
    int  length;
}sstring, *Lstring;
Status  Init_String(SString  &S)//切记使用"&",因为初始化，需用将实参改变，一定用引用，否则，只是形参改变，而实参并没有改变
{
    S.base = (char*)malloc(MAXLENG*sizeof(char));
    if (!S.base)  printf("分配失败");
    S.length = 1;//为了计算next的方便，这里不适用0号位置
    char  ch;
    printf("请输入一个字符串：");
    ch = getchar();
    while (ch != '\n')
    {
        S.base[S.length] = ch;
        S.length++;
        ch = getchar();
    }
    return  1;
}
int next[MAXLENG];
//j为串的第j个字符；k为第j个字符之前的最大匹配前缀和后缀
void  Next(SString t)
{
    int j = 1;
    int  k = 0;
    next[1] = 0;
    while (j < t.length)
    {
        if (k == 0 || t.base[k] == t.base[j])
        {
            k++;
            j++;
            next[j] = k;
        }
        else 
        {
            k = next[k];
        }
    }
    //printf("%d\r\n",t.base[0]);
    for (int i=1; i < t.length; i++)
    {
        printf("%d",next[i]);
    }
}
Status   Make_Kmp(SString  S, SString  T,int &e)//主串与模式串相互比较，并返回相同字符时在主串中的第一个字符位置
{
    Next(T);
    int  i = 1;
    int  j = 1;
    while (i < S.length&&j < T.length)
    {
        if (j==0||S.base[i] == T.base[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
        if (j>= T.length)
        {
            e = i - T.length+1;
            printf("\r\n%d,%d\r\n", i, T.length);
            printf("从第%d个位置开始匹配", e);
        }
        if (i >= S.length)
        {
            printf("主串中，没有该字符串");
        }
    }
    return  0;
}
/*Status  Insert_Char(SString  &S, char  ch)
{
    if (S.length == MAXLENG)
    {
        S.base = (char*)realloc(S.base, (MAXLENG + INCREMENT));
        if (!S.base)
        {
            printf("分配空间失败");
            return  -1;
        }
    }
    S.base[S.length] = ch;
    S.length++;
    return  1;
}*/
Status  Travel(SString  T)
{
    for (int i = 1; i < T.length; i++)
    {
        printf("%c",T.base[i]);
    }
    return  0;
}
int main()
{
    SString  T;
    SString  S;
    int  e;
    char  ch;
    Init_String(T);
    Init_String(S);
    Next(T);
    Travel(T);
    Travel(S);
    printf("\r\nkmp算法开始进行模式匹配：\r\n");
    Make_Kmp(S,T,e);
    return 0;
}