KMP算法里面的next数组：对于索引到底是从0还是1开始的分析(基于荣政版数据结构与算法分析)

KMP算法里面的next数组，分析起来还是挺有味道的，书上的文字描述看起来有点杂乱，然后上网查就更懵了，b站啊各种论坛啊，写的人多但是会发现他们之间有一些不一样，我觉得区别就在于那个数组下标到底是从0还是从1开始的、、、

现在说一下我自己的理解吧（假设看到这篇博客的人是已经会手算next数组的哈，我就直接上代码了）

文章目录

1.数组下标问题2.next数组的定义：3.现在分析荣政老师书上的代码：4.关于荣政老师代码的一点问题5.下标从1开始的next代码

1.数组下标问题

编程语言里面的数组，都是从0开始的，即定义一个arr[10]，那么它里面是从a[0]~a[9]的，然而由时候可能为了运算方便或其他作用，我们常使用a[1]~a[9]来存实际数据元素，所以得具体看题目要求啊 数组下标从0开始：即数组里面从第一个到最后一个存的都是数组元素 数组下标从1开始：任然是有arr[0]存在的，不过它不存数组元素，可以存一下辅助信息，比如数组元素的实际个数 eg：定义一个数组为arr[10]，但是第一位不存数组元素，第二位到第十位才存，假如现在第一位存数组元素实际个数，现在我把abcdefg存进去，那么现在数组里面的情况是这样的，对了，从1开始不代表有a[10]啊，底层仍然是a[0]~a[9]

2.next数组的定义：

就可以看到这里其实next数组下标是从1开始的

3.现在分析荣政老师书上的代码：

void GetNext(seqstring *t, int *next) { int i = 0, j = -1; next[0] = -1; while (i < t->len) { if (j == -1 || t->ch[i] == t->ch[j]) { ++i; ++j; next[i] == j; } else { j = next[j]; } } }

这里推荐一篇我认为写得最好的kmp算法博客点这里，其他的博客真的一言难尽，大家在查找的时候可要费些功夫了 可以看到这里next[0]=-1，所以这个代码的next下标是从0开始的，而上面next的定义说了，是下标是从1开始的，好，慢慢来 因为我的visual studio出了点问题，所以我用java复现一下代码，原理一样的，就是一些定义不一样，相信都可以看得懂， 基于书上的例4-2里面的T="abaabcac"

static void getNext0(char[] s,int[] next){ int i = 0,j = -1; next[0] = -1; while (i < s.length){ if (j == -1 || s[i] == s[j]){ ++i; ++j; next[i] = j; }else { j = next[j]; } } } public static void main(String[] args) { char[] s0 = {'a','b','a','a','b','c','a','c'}; int[] next0 = new int[9]; getNext0(s0, next0); for (int i = 0; i < 9; i++) { System.out.print(" " + next0[i] + " " ); } }

运行结果： 发现什么问题没有，书上的结果是： 问题1：结果完全不对啊！问题2：这里是8个数据而我上面运行出来是9个数据 好了，这就是下标从1开始还是0开始带来的不同影响

先解决为什么是9个数据的问题：注意看代码，while (i < s.length)，而在它里面是先++i，在进行赋值next[i]=j，这就导致当i=7时，while放行，++i使得i=8，所以此时就出现了next[8]，所以也就有了9个元素；

再说结果的问题：虽然完全不一样，但是注意看，我的运行结果全部加1，即为正确结果，当然这个时候就舍弃掉我多出来的最后一个数据，保留前8个，为什么加1呢，原因就在于看初始定义next[0]=-1，而回看next数组定义，里面的第一个值定义的是0，了解了吧

4.关于荣政老师代码的一点问题

可以看到代码里面，j的初始值是-1，而在if (j == -1 || s[i] == s[j])这里却直接使用j来作为数组下标，难度数组还有下标为-1的吗，其实不然，注意这里的||符号，它是或的意思，即一个正确就放行，两个都错误才退出，那么一开始，我的j值为-1，是不是第一个就正确的，所以此时就不用再判断后面的s[i] == s[j]了，也就不会出现错误了，那么当第一个错了怎么办呢，第一个错j就不是-1了，所以下标也就不会出错了，但是得注意，不要写为if(s[i] == s[j] || j == -1)，一旦反过来，就会先判断前面一个，此时就会报数组越界的错误了

5.下标从1开始的next代码

要是题目要求下标从1开始，就得改变一下代码了，而且此时得出的结果即为正确结果，不用像第一种代码那样需要丢弃最后一个结果并且全部加1才是正确结果，我就把两种代码一起贴出来

public class KMP { // 下标从1开始 static void getNext(char[] s,int next[]){ int i = 1,j = 0; next[1] = 0; while (i < s.length-1){ if (j == 0 || s[i] == s[j]){ ++i; ++j; next[i] = j; }else { j = next[j]; } } } //下标从0开始 static void getNext0(char[] s,int[] next){ int i = 0,j = -1; next[0] = -1; while (i < s.length-1){ // 把这里改一下减1，就不会出现多一个数据的情况了 if (j == -1 || s[i] == s[j]){ ++i; ++j; next[i] = j; }else { j = next[j]; } } } public static void main(String[] args) { char[] s = {'9','a','b','a','a','b','c','a','c'}; int[] next = new int[9]; getNext(s, next); for (int i = 1; i < 9; i++) { System.out.print(" " + next[i] + " " ); } System.out.println(""); char[] s0 = {'a','b','a','a','b','c','a','c'}; int[] next0 = new int[8]; getNext0(s0, next0); for (int i = 0; i < 8; i++) { System.out.print(" " + next0[i] + " " ); } } }

运行结果： 可以发现：从1开始的即为正确结果，而从0开始的需要加1才是正确结果

两种代码的区别在于： 1.初始化的是i与j的不同，还有next的初始化 2.待验证数组的不同，从1开始的，如上面分析的，第一位就不存元素，而存实际个数等辅助信息

还有就是改动那里，减1就可以避免多跑出来一个数据的问题，