高效计算nextval数组值：字符串匹配算法的简便方法解析

模式串t=‘abcaabbabcab’，求nextnextval的值

第一个数字的下一个值为0，第二个数字的下一个值为1。
后面求解每个数字的下一个值时，根据前一个数字进行比较。
比较前一位和后一位对应的内容。
如果相等，则该位的下一个值是前一个位的下一个值加1。

如果不相等，则继续查找下一个值对应的内容与前一个位进行比较，直到发现某一位的内容的下一个值对应的内容与前一个位相等，则该位对应的值加1就是所需要的下一个值。
如果即使找到第一位也没有找到与前一位相同的内容，则所需位上的下一个值为1。

计算第三位的下一个值时，查看前一个数字（序号2）b（两者都与这个b进行比较）。
如果下一个值为1，则序号1对应于a和b不同。
，没有前一个数字，因此第三个下一个值为1。

扩展信息：

注释：

1.查找next函数值和nextval值时，必须获取前缀字符串和后缀字符串之间最长的相同字符串。

2.字符串匹配中，()用于保存字符串，[]用于定义匹配字符范围，{}用于表示匹配长度。

3.如果相同，则i和j分别+1，继续比较S[1]和T[1]。
（在该示例中，S[1]=T[1]=b）。

4.直到出现差异S[i]!=T[j]。
（在该示例中，S[2]=c！=T[2]=d）。

参考来源：百度百科-字符串匹配

求nextval数组值的简便方法

而如果你还记得我推荐的方法，你就可以随时轻松解决nextval。
首先我们看看如何求解下一个数组值。
示例：模式字符串abaabcacnextvalue01122312nextvalvaluenext数组求解如下：第一个数字的下一个值为0，第二个数字的下一个值为1。
稍后，在求解每个数字的下一个值时，将其进行比较相应地到前一个数字。
首先比较前一位的内容和下一位的值。
如果相等，则该位的下一个值是前一个位的下一个值加1。
如果不相等，则继续查找下一位对应的内容进行比较，直到找到对应的内容。
下一个值与前一个位匹配。
那么该位对应的值加1就是需要的下一个值；如果找到第一位而没有找到内容。
如果前一位相等，则所需位中的下一个值为1。
这似乎令人困惑。
我们通过上面的例子来了解一下。
1.前两位必须是0和1。
2.计算第三位时，考虑第二位b的下一个值。
如果是1，比较b和a，对应的是1。
如果不同，则第三位a的值为1，因为只有比较前一位才出现相同的比较现象。
3.计算第四位时，考虑第三位a的下一个值。
如果是1，则将a与1对应的a进行比较。
如果相等，则第四位的下一个值为a，第三位的下一个值为a。
将值加1。
为2。
因为是在第三位实现的，所以下一个值对应的值与第三位的值相同。
4.计算第五位时，考虑第四位中a的下一个值。
如果是2，则将a与等于2的b进行比较。
如果不同，则比较b的下一个值，等于1。
将a与第四位比较，则第五位的下一个值是第二位b的下一个值加1，即2。
在第二位实现时，下一个值对应的值与第四位的值相同。
5.计算第六位数字时，考虑第五位数字b最接近的值。
如果是2，则将b与2对应的b进行比较。
如果它们相等，则第六位的下一个值为c。
加1，即3，因为下一个值对应的值是在第五位实现的，与第五位相同。
6.计算第七位时，考虑第六位c的最接近值。
如果是3，则比较c和3对应的a。
如果不同，则将第三位a的下一个值1与a对应的第三位进行比较。
如果仍然不同，则第七位的下一个值为1。
7.计算第八位查看第七位a的下一个值为1，将a与a进行比较，则1对应。
如果相等，则第八位c的下一个值是第七位a的下一个值加1，即2，因为它在第七位，其下一个值对应的值与第七位相同少量。
在计算nextval之前，首先要了解nextval是在某些情况下生成的，是为了弥补next函数的缺点。
例如，如果主字符串是“aaabaaaab”，模式字符串是“aaaab”，就会浪费一些东西情况：当比较主字符串和模式字符串的第四位时，发现它们的值不是相同。
根据我们的观察，我们可以直接从主串的第五位开始与模式串进行比较，但实际上是这样的。
进行了多次冗余比较。
使用nextval删除不必要的比较。
有两种方法可以通过直接观察来查找nextval数组值，而不依赖于next数组值。
两种方法都可以使用，具体取决于您喜欢使用哪种方法。
。
我们使用“aaaab”示例来检查第一种方法。
1.想象一下，在模式匹配过程中，将模式串“aaaab”与主字符串进行匹配时，如果第位数字不匹配，则不需要进行比较和移位，即第一位数字不是a，直到主字符串的下一位与模式字符串继续让我们比较第一个位置。
此时，模式串还没有移动。
那么模式串中第一个a的nextval值为0。
2.在匹配过程中，如果仅在第二个位置发生不匹配，那么主串的第一个数字一定是a，并且第二个数字不能是a.由于我们知道第二个数字不能是a，因此无需比较主字符串的第一个和第二个数字。
我们直接跳到第三个数字，将其与模式字符串的第一个数字进行比较。
比较位。
同样，模式串未偏移的值仍为0。
3.第三、第四位与2的过程类似，都是0。
4.如果匹配过程中仅在第五位出现不匹配，则从第一个到第五位主字符串第四位必须是a，第五位不能是b，但第五位仍然可以等于a。
如果第五位是a，则第一个字符串会匹配成功，因为前四位都是a，第六位是b。
因此，目前情况下，需要检查第五个位置是否为a。
于是进行如下比较：123456aaaa**aaaabaaaab。
前面的三个A不需要比较。
只要判断主串中的位是否不等于B，就可以进行如下比较：如果是a，则继续比较主串的最后一位是否是b。
如果不是a，则比较结束并继续将模式串的第一个数字与主字符串的下一个数字进行比较。
从这个角度来看，对模式串的第五位进行了4位的比较（没有偏移，下一位直接与0进行比较），所以第五位b的nextval值为4。
我们可以使用第一个例子“abaabcac”来验证这个方法。
a的nextval值为0，因为如果主字符串的第一位不是a，则不需要进一步比较。
直接比较第二位数字是否主要字符串是a。
如果比较主串第二位出现错误，则主串第一位必须是a，第二位不能是b。
此时不能直接跳转到第三位进行比较，第二位也可以是a，所以再次比较主串的第二位，偏移1位，所以第二位的下一个值。
模式字符串为1。
同样，Nextval值为：01021302。
之所以第六位的next值为3，是因为如果主字符串与第六位比较时出现不匹配，则主字符串的前五位是“abaab””必须是，并且第六位数字不能是“abaab”。
但是，如果第六位是“a”，我们可以从模式串的第四位开始继续比较。
因此，这个比较是：123456789101112abaab********abaabcac而不是：123456789101112abaab*******abaabca由于前两个a和b已经确定，所以不需要比较，因此模式串第六位的下一个值为偏移3。
为了进行比较，我们看一下查找nextval数组值的第二种方法，模式字符串abaabcacnextvalue01122312nextvalvalue010213021。
如果第二个数字与第一个数字0相同，则第一个数字的nextval值必须为0，2、接下来第三位的值为1，然后比较第三位位置与第一个位置，均为a且相等，则第三位的nextval值为0。
3.第四位的nextval值为2，然后比较第四位和第二位。
如果不同，则第四位的下一个值为2。
下一个值为2。
4。
第五位的下一个值为2。
然后将第五位与第二位进行比较。
如果相等，则第二位的下一个值为1，然后将第二位进一步与第一位进行比较。
如果不同，则第五位的下一个值是第二位的下一个值是1。
5。
第六位的下一个值是3。
然后比较第六位和第三位。
如果不同，则第六位的下一个值ne值为2，然后将第八位与第二位进行比较。
如果不同，则第八位的下一个值是其下一个值，即2。
检查“aaaab”内。
模式字符串aaaa最佳值01234下一个值00004