【数据结构】KMP手工计算next数组和nextval数组

╰+哭是因爲堅強的太久メ 2022-04-17 01:41 245阅读 0赞

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值，但是如果是考试，那就只能自己来手算这两个数组了，这里分享一下我的计算方法吧。

计算前缀 Next\[i\] 的值:

我们令 next\[0\] = -1 。从 next\[1\] 开始，每求一个字符的 next 值，就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是，这2个"字符串"不能是同一个"字符串")。如果一个都没有，这个字符的 next 值就是0；如果有，就看它有多长，这个字符的 next 值就是它的长度。

计算修正后的 Nextval\[i\] 值:

我们令 nextval\[0\] = -1。从 nextval\[1\] 开始，如果某位(字符)与它 next 值指向的位(字符)相同，则该位的 nextval 值就是指向位的 nextval 值(nextval\[i\] = nextval\[ next\[i\] \])；如果不同，则该位的 nextval 值就是它自己的 next 值(nextvalue\[i\] = next\[i\])。

### 举个例子:求 模式串"ababaaababaa"的next数组和nextval数组。 ###

![20181111145557295.png][]

求以上串的next数组和nextval数组。

1 关于next数组的求法(从0开始)

S:代表串 next:为next数组  nextval:为nextval数组 k=1 j=1为标志位

1）赋初值next\[1\]=0 next\[2\]=1

2）s\[1\]!=s\[2\],则 j++,k,next\[j\]=next\[3\]=1;

3）s\[1\]==s\[3\],则 j++,k++,next\[j\]=next\[4\]=k=2;

4）s\[2\]==s\[4\],则j++,k++,next\[j\]=next\[5\]=k=3;

5）s\[3\]==s\[5\],则j++,k++,next\[j\]=next\[6\]=k=4;

6） s\[4\]!=s\[6\],则j++,k, k返回到next\[k\]位置，即k=next\[4\]=2,然后比较S\[k=2\] != S\[6\] ,所以再令k=next\[2\]=1,s\[1\]==s\[6\],则 j++,k++,next\[7\]=2;

7) s\[2\]!=s\[7\],令k=next\[2\]=1,s\[1\]==s\[7\],则j++,k++,next\[8\]=2;

8) s\[2\]==s\[8\],则 k++,j++,next\[j\]=next\[9\]=3;

9) s\[3\]==s\[9\],则 k++,j++,next\[j\]=next\[10\]=4;

10) s\[4\]==s\[10\],则 k++,j++,next\[j\]=next\[11\]=5

11) s\[5\]==s\[11\],则 k++,j++,next\[j\]=next\[12\]=6

### 则 next 数组为：0,1,1,2,3,4,2,2,3,4,5,6 ###

求nextval数组

计算修正后的 Nextval\[i\] 值:

nextval\[1\] = 0;定值。  
s\[2\] != s\[next\[2\]\]，nextval\[2\] = next\[2\] = 1, 则 nextval\[2\] = 1;  
s\[3\] == s\[next\[3\]\]，nextval\[3\] = nextval\[next\[3\]\] = 0则nextval\[3\] = 0;  
s\[4\] == s\[next\[4\]\]，nextval\[4\] = nextval\[next\[4\]\] = 1则nextval\[4\] = 1

s\[5\] == s\[next\[5\]\]，nextval\[5\] = nextval\[next\[5\]\] = 0则nextval\[5\] = 0;  
s\[6\]!= s\[next\[6\]\]，nextval\[4\] = next\[6\] =4则nextval\[6\] = 4

s\[7\] != s\[next\[7\]\]，nextval\[7\] = next\[7\] = 2则nextval\[7\] = 2  
s\[8\] == s\[next\[8\]\]，nextval\[7\] = nextval\[next\[8\]\] =1。nextval\[8\] =1

s\[9\] == s\[next\[9\]\]，nextval\[9\] = nextval\[next\[9\]\] =0。nextval\[9\] =0

s\[10\] == s\[next\[10\]\]，nextval\[10\] = nextval\[next\[10\]\]= 1则nextval\[10\] = 1  
s\[11\] == s\[next\[11\]\]，nextval\[11\] = nextval\[next\[11\]\]= 0则nextval\[11\] = 0  
s\[12\] == s\[next\[12\]\]，nextval\[12\] = nextval\[next\[12\]\]= 1则nextval\[12\] = 4

### nextval数组为：0,1,0,1,0,4,2,1,0,1,0,4 ###

[20181111145557295.png]: /images/20220417/9bb9a4028ab2495c96258765af6646ae.png