KMP算法

对于多数算法理解了算法的意思与过程方式，基本就了解了一大半，但是，但是当我自己写next[]时人还是懵的，上百度，可是还是有些不理解，最后看到一个博主他的经历和我差不多他把他经历讲了一遍，说看书碰到p.str[i]!=p.str[j],j就要回退，书上一开始就是这样，我看的有点懵圈，最后我就按照算法一个个来，经过脑子一大圈转弯之后终于理解了，首先得了解为什么要创建next[]，
下面void getnext(seqstring p, int next[])就是从开头开始，就是前缀和后面地一直比较事否相等，如果相等，就往后一起移动，否则，前面地比较要回溯到初始开始在和后面比较，就可以了，这是我自己理解地最接地气地解释了，第一次自己把自己地想法来分享下。fighting！！

#include <stdio.h>
# define max 100
typedef struct{
     char str[max];
      int length ;
}seqstring;

void getnext(seqstring p, int next[])  //next[]值的计算 和输出next【】值
{
   int i,j;
   next[0]=-1;   i=0;  j=-1;
   while( i<p.length )
   {    if( j==-1 || p.str[i]==p.str[j] )
        { ++i; ++j; next[i]=j; }
        else    j=next[j];
   }
   for(i=0;i<p.length;i++)
      printf("%5d", next[i]);
}
int kmp(seqstring t  /*主串*/, seqstring p /*模式串*/, int next[])
{
   int i=0,j=0;
   while (  i<t.length && j<p.length  )
   {   if(  j==-1 || t.str[i]==p.str[j]  )
       { i++; j++; }
       else  j=next[j];
   }
   if ( j==p.length )   return (i-p.length);
   else return(-1);
}
seqstring insert(seqstring p)  //储存字符串
{
     char x;
    scanf("%c",&x);
    int i=0;
    while(x !='#')
    {
      p.str[i++]=x;
      p.length=i;
      scanf("%c",&x);
    }
    i--;
    printf("\n");
    return p;
}
int main()
{
    seqstring a,b;
    printf("请输入模式串且模式串小于max(以 ’#‘ 结束\n");
    a=insert(a);
    int next[max];
     getnext( a,next);

    printf("\n请输入主串(以#结束)\n");
    b=insert(b);
    int k;

    k=kmp( b,a, next);
    if(k==-1)
        printf("匹配失败\n");
        else
    printf("匹配位置在第%d位置上\n",k);


}