为什么KMP匹配算法的next[1]为0

Question

今天学习KMP匹配算法时，注意到next[j]当j=1时似乎要取0，为什么是这样呢？

KMP匹配算法里面的next[ ]不是用来统计到目前为止有多少个公共前后缀吗，在《大话数据结构》以及我查阅的很多资料中，像模式字符串abcabx,它的next[ ]应当是 011123,这是我不太能理解的。我认为next[] 应该是 000120，而且我用这样的next[ ]似乎实现了同样的功能，即避免i值回溯，以实现时间复杂度为O(m+n)。

我想知道我的实现方法是否可行，然后我还想知道书上和一些资料里面的next[ ]到底是怎么来的，它对我来说似乎过于抽象了，我理解不了。

#include<stdio.h>
#include<windows.h>
#include<stdlib.h>

void getNext(int* next,char pattern[],int length);
int KMP_search(char *s,char *p,int pos,int p_length,int s_length);

int main()
{
    char p[] = "abcabx";
    char s[] = "babcabxss";
/*     int l = sizeof(p)/sizeof(p[0]) - 1;
    int next[l];
    getNext(next,p,l);
    for(int i =0;i<l;i++)
    {
        printf("%d ",next[i]);
    } */
    int p_length = sizeof(p)/sizeof(p[0])-1;
    int s_length = sizeof(s)/sizeof(s[0])-1;
    int pos = KMP_search(s,p,0,p_length,s_length);
    printf("%d ",pos);
    system("pause");
}

void getNext(int* next,char pattern[],int length)
{
    next[0] = 0;
    int i = 0,j = 1;
    while(j<length)
    {
        if(pattern[j] == pattern[i])
        {   
            next[j] = i+1;
            j++;
            i++;
        }
        else if(i == 0)
        {
            next[j] = i;
            j++;
        }
        else
        {
            i = next[i];
        }
    }
}

int KMP_search(char *s,char *p,int pos,int p_length,int s_length)
{
    int i = pos;
    int j = 0;
    int next[256];
    getNext(next,p,p_length);
    while(i<s_length&&j<p_length)
    {
        if(s[i] == p[j])
        {
            i++;
            j++;
        }
        else if(j == 0)
        {
            i++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j == p_length)
    {
        return i-j;
    }
    else
    {
        return -1;
    }
}

Answer 1

next 数组考虑的是除当前字符外的最长相同前缀后缀，因为除了当前字符外，1前面只有一个字符，不可能会出现公共前缀的，所以next(1)是0