#include <stdio.h>
#include <string.h>
void KMP(char *p , int *next)
{
    int length;          //模式串长度
    int j=0;            //next数组的下标   
    int k=-1;           //next数组下标的值
    length = strlen(p);
    next[0]=-1;
    while( j< length)     //next数组赋值
    {
        if (k == -1 || p[j] == p[k])      
        {
            j++;
            k++;
            if ( p[j] != p[k])
                next[j]=k;
            else
                next[j]=next[k];
        }
        else
            k=next[k];                //  这里想不通，为什么不直接  k=-1呢？  
    }   
}
int main()
{   
    char text[30];
    char pattern[30];
    int next[30];
    int i=0,j=0;                // i为文本串数组下标，j为模式串下标
   
    printf("请输入文本串");
    scanf("%s",text);
    printf("请输入模式串");
    scanf("%s",pattern);
   
    KMP(pattern,next);                  //获取next数组
   
    int textlength,patternlength;   
    textlength = strlen(text);
    patternlength = strlen(pattern);
   
    while(i <= (textlength-patternlength) )
    {
        while(j==-1 || (pattern[j] == text[i] && pattern[j]!='\0'))
        {
            i++;
            j++;
        }
        if(j == patternlength)
        {
            printf("success");
            return 0;
        }
        
        j=next[j];
        
    }
    printf("failed");
    return 0;
}


next数组不是比较 0~k-1  和 (j-k)~(j-1)  的字符是否相同吗？

那不同后为什么不直接把k返回-1，而是k=next[k]？

能不能举个例子使用k=-1后与使用k=next[k]后的next数组不同？谢谢了

[ 本帖最后由 wqwqyt123 于 2015-7-6 22:28 编辑 ]

额，虽然看不懂你在说什么。。但我实在受不了不懂这玩意，自己想了一个挺长的模式串自己分析，懂了
ababc ababd ababc ababc g


  k= -1  0  0  1  2  0  1  2  3  4
  j=  0  1  2  3  4  5  6  7  8  9
  k=    -1       -1             (2->-1)

      a  b  a  b  c  a  b  a  b  d

next  -1 0  -1 0  2  -1 0  -1 0  4


    k=   0  1  2  3  4  5  6  7  8  9
    j=  10 11 12 13 14 15 16 17 18  19
    k=                              4

         a  b  a  b  c  a  b  a  b  c

next    -1 0  -1 0  2  -1 0  -1 0  4


    k=   5
    j=   20
    k=
         g
   next  5


如果 k=-1   那 next[20]=0

发现自己好无聊，把上面的玩意打了出来