串abbabc的next值为（）

[问答题]

串abbabc的next值为（）

张小头

下标	0	1	2	3	4	5
	a	b	b	a	b	c
next	0	1	1	1	2	3
nextval	0	1	1	1	1	3

（默认数组从1开始的结果为上图，如果为0的话，结果为所有值减1）

next数组求法：当模式串的i位匹配失败时，在它之前的i-1子串求最长相等前后缀长度+1，前缀长度指的是模式子串包含第一个字母的前n个字母组成的串，后缀长度类同，就是包含最后一个字母的后n个字母组成的串，找到相同的前后缀串的长度+1就是对应next数组的值，比如表格中的最后一个c，他的i-1子串为abbab，我们找到他相等的前后缀为ab，ab的长度为2，所以最后一个c对应的next数组的值就为2+1=3。

nextval数组的求法：在next数组的基础上，如果next j是同样字符，则把下标小的next值赋值给下标大的next值。

发表于 2021-02-21 14:52:02 回复(0)