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

(53) 2024-06-04 20:01:01

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]
nextval和next数组区别_串的next数组值详细步骤 (https://mushiming.com/)  第1张

2.next数组的定义:

nextval和next数组区别_串的next数组值详细步骤 (https://mushiming.com/)  第2张
就可以看到这里其实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] + " " );
    }

    }

运行结果:
nextval和next数组区别_串的next数组值详细步骤 (https://mushiming.com/)  第3张
发现什么问题没有,书上的结果是:
nextval和next数组区别_串的next数组值详细步骤 (https://mushiming.com/)  第4张
问题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] + " " );
    }

    }

  }

运行结果:
nextval和next数组区别_串的next数组值详细步骤 (https://mushiming.com/)  第5张
可以发现:从1开始的即为正确结果,而从0开始的需要加1才是正确结果

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

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

THE END

发表回复