nextval和next数组区别_串的next数组值详细步骤

KMP算法里面的next数组，分析起来还是挺有味道的，书上的文字描述看起来有点杂乱，然后上网查就更懵了，b站啊各种论坛啊，写的人多但是会发现他们之间有一些不一样，我觉得区别就在于那个数组下标到底是从0还是从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就可以避免多跑出来一个数据的问题，