-
{草履虫都能看懂的} 数据结构串的PM、next和nextval数组的求法
一、PM数组的求法（求next数组的第一个步骤）
前缀、后缀和最长相等前后缀：
前缀指除最后一个字符外，字符串的所有头部子串；后缀指除第一个字符外，字符串的所有尾部子串。
头部子串：包含头部
尾部子串：包含尾部
如：
‘a’ 的前缀和后缀都为空集，最长相等前后缀长度为0；
‘ab’ 的前缀为 {a} , 后缀为 {b} ，最长相等前后缀长度为0，因为这两个集合交集为空集，空集长度为0；
‘abab’ 的前缀为 {a, ab, aba}，后缀为 {b, ab, bab}，最长相等前后缀长度为2，即交集 {ab} 的字符长度。求PM数组
假设串 S = ‘ababaaababaa’
对第一个字符 ‘a’ ，求出最长相等前后缀为 0；
对前两个字符 ‘ab’ ，求出最长相等前后缀为 0；
对前三个字符 ‘aba’ ，求出最长相等前后缀为 1；
对前四个字符 ‘abab’ ，求出最长相等前后缀为 2；
… …
对所有串 ‘ababaaababaa’，求出最长相等前后缀为 6；
得到一个表串 S a b a b a a a b a b a a PM数组 0 0 1 2 3 1 1 2 3 4 5 6 二、next数组的求法
得到上述PM数组后
将PM值向右移1位，最左边补-1即得到next数组串 S a b a b a a a b a b a a PM数组 0 0 1 2 3 1 1 2 3 4 5 6 Next数组 -1 0 0 1 2 3 1 1 2 3 4 5 这个next数组合法，整体值加一也合法
即
next数组一：-1 0 0 1 2 3 1 1 2 3 4 5
next数组二：0 1 1 2 3 4 2 2 3 4 5 6
上述两个next数组属于同一个，next数组一表示串的位序从0开始，next数组二表示串的位序从1开始；三、nextval 数组的求法
得到next数组后要想求nextval数组，需要将next数组表示为串的位序从1开始的形式，即第二步中的
next数组二串 S a b a b a a a b a b a a PM数组 0 0 1 2 3 1 1 2 3 4 5 6 Next数组 0 1 1 2 3 4 2 2 3 4 5 6 Nextval数组 0 首先Nextval数组的第一值是0，如上表所示，这个要记住
然后记住要领相等取nextval数组，不相等取next数组
意思如下：
求nextval数组第二位时，串的值对应 ‘b’ ，'b’对应的next值是 1 ，意思是 ‘b’ 和第一位字符 ‘a’ 比较，它们不相等 即 ‘a’ != ‘b’ ，所以值为next数组对应的值 1
得到第二位的nextval值串 S a b a b a a a b a b a a PM数组 0 0 1 2 3 1 1 2 3 4 5 6 Next数组 0 1 1 2 3 4 2 2 3 4 5 6 Nextval数组 0 1 同理，求第三位时
串 S a b a b a a a b a b a a PM数组 0 0 1 2 3 1 1 2 3 4 5 6 Next数组 0 1 1 2 3 4 2 2 3 4 5 6 Nextval数组 0 1 0 按照上述两个步骤要领，得到所有的nextval值
串 S a b a b a a a b a b a a PM数组 0 0 1 2 3 1 1 2 3 4 5 6 Next数组 0 1 1 2 3 4 2 2 3 4 5 6 Nextval数组 0 1 0 1 0 4 2 1 0 1 0 4 -
相关阅读:
JavaScript系列之Array对象
C++ merge()和inplace_merge()函数用法详解(深入了解,一文学会)
Unreal 输入系统 解析
rocketmq集群搭建笔记
HIve数仓新零售项目DWD层的构建
【产品经理修炼之道】- 从0到1搭建风筝比赛小程序
Java 集合框架，泛型，包装类
打造硬核敲门砖——简历
6.824 lab1
英文网站的优化怎么判断是否到位
- 原文地址：https://blog.csdn.net/qq_56039091/article/details/125528577