Question

关于KMP算法，next第一个值到底是什么？！

在严老师的课本上，求NEXT的时候，是从next[1] = 0开始的，但是网络上很多的博客神马的，求next都是从next[0] = -1开始的。。。并且两种方法求出的next值完全不一样，求大神解释下

Answer 1

上代码,有详细说明
public class KMP {

String model = "abcdabce";
// String model = "abcabcabd";
// String model = "aaaab";
// String model = "asdaaaaaaabdabcabcaabaaaaaskdf";
char[] tempModel = model.toCharArray();

String str = "asdaaaaaaabdabcabcaabaaaaaskdf";
char[] tempStr = str.toCharArray();

int[] backto = new int[model.length()];
int[] next = new int[model.length()];

//查找用例
public void findStr(){
int i=0;
int j=0;
while(i<tempStr.length){
if(tempStr[i] == tempModel[j]){
i++;
j++;
}else{
j = backto[j];
if(j<0){
i++;
j++;
}
}

if(j == tempModel.length){
System.out.println(i+" "+tempStr[i-1]);
j=0;
}
}
}

/**
* a a a a b
* -1 -1 -1 -1 3
*
* a b c d a b c e
* -1 0 0 0 -1 0 0 3
*/
public void next(){
int i=0, //模式串下标,即当前位置.开始为0
k=-1;//k表示字符串在位置i之前已匹配的子串最长长度.类似于模式串的下标(从0开始)
next[i]=-1;//第一个next为-1
while(i+1<tempModel.length){//i 模式串的当前位置,因为第一个next为-1,所以从第二个开始,往前查找模式长度
if(k == -1 //初始,k,i直接自加:k=0,i=1
|| tempModel[k] == tempModel[i]){//比较第k个字符和第i个字符
i++;
k++;
if(tempModel[k] != tempModel[i]){//比较第k+1个字符和第i+1个字符不相等,说明k为当前模式最长长度.
next[i] = k;//k最小为0,因为i是从第二个开始的
}else{//第k+1个字符和第i+1个字符相等,说明第i+1个字符比较不同后,可后推到第next[k]个字符开始比较
next[i] = next[k];
}
}else{//往后找k值,此时k值表现为模式串的下标
k = next[k];
}
}
}

public void start(){
System.out.println("--------------------------------");
next();
//CommonUtil.printCharAndIntArray(tempModel,next);
}

public static void main(String[] args){
new KMP().start();
}
}

Answer 2

就KMP本身算法来讲，从0开始的是PMT（partial match table）, 代表的是pattern中截至第i 位的前后缀匹配长度，而我们在使用PMT做字符串匹配时，如果是在pattern的 i 位与目标字符串失配，那么影响回溯的位置的其实是第 i -1 位的 PMT 值，所以为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位，而后移一位得出的表或者数组就是所谓的Next，至于-1并不是很重要，仅是一个标记符

Answer 3

其实是一样的，区别在于子串在数组中是从0还是1开始存储。next值整体前后移动一位而已。