在字符串匹配问题中，常常会用到模式串的next数组和nextval数组，这两个数组用于加速字符串的匹配过程。
1. next数组的计算：
next[i]的值表示模式串t中，以第i个字符结尾的前缀字符串与后缀字符串的最长公共部分的长度。具体计算方法如下：
（1）首先求出模式串t的长度，假设为m；
（2）初始化next数组的第一个元素next[0]为-1；
（3）遍历模式串t的每个字符，假设当前遍历的字符是t[i]： - 初始化j = next[i - 1]，j表示最大的相同前后缀的长度； - 如果t[j] == t[i]，说明下一个最长的相同前后缀长度可以加1，即next[i] = j + 1；
-如果t[j]!=t[i]，则需要不断向前回溯，直到找到一个长度更小的相同前后缀，或者回溯到开始位置；
-重复上述过程，直到遍历完整个模式串。 2. nextval数组的计算：
相对于next数组来说，nextval数组的计算过程更为复杂，但是在一些情况下，它的效率更高。具体计算方法如下：
（1）首先求出模式串t的长度，假设为m；
（2）初始化nextval数组的第一个元素nextval[0]为-1；
（3）遍历模式串t的每个字符，假设当前遍历的字符是t[i]： - 初始化j = nextval[i - 1]，j表示最大的相同前后缀的长度； - 如果t[j] == t[i]，说明下一个最长的相同前后缀长度可以加1，即nextval[i] = j + 1；
-如果t[j]!=t[i]，则需要继续向前回溯，寻找到一个长度更小的相同前后缀；
-如果t[j]!=t[i]，则需要继续向前回溯，寻找到一个长度更小的相同前后缀；
-如果j=-1，说明已经回溯到模式串的开始位置；
-如果t[j]==t[i]，说明找到了一个长度更小的相同前后缀； - 根据上述步骤的结果，得到nextval[i]的值。
需要注意的是，计算next数组和nextval数组的过程都是从模式串的第二个字符开始的，所以需要先初始化数组的第一个元素为-1
下面以一个例子来具体说明如何计算next数组和nextval数组： 假设模式串t为\"ABCDABD\"，则模式串的长度为7 首先计算next数组：
- t[0]前面没有字符，所以next[0] = -1； - 遍历到t[1] = 'B'，此时j = next[0] = -1；
- t[j] = t[-1]，跳过此步骤，直接执行next[1] = 0； - 遍历到t[2] = 'C'，此时j = next[1] = 0；
-t[j]!=t[2]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行next[2] = 0； - 遍历到t[3] = 'D'，此时j = next[2] = 0； -t[j]!=t[3]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行next[3] = 0； - 遍历到t[4] = 'A'，此时j = next[3] = 0； -t[j]!=t[4]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行next[4] = 0； - 遍历到t[5] = 'B'，此时j = next[4] = 0； -t[j]!=t[5]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行next[5] = 0； - 遍历到t[6] = 'D'，此时j = next[5] = 0； -t[j]!=t[6]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行next[6] = 0； 所以模式串t的next数组为：[-1, 0, 0, 0, 0, 0, 0]。 接下来计算nextval数组：
- t[0]前面没有字符，所以nextval[0] = -1； - 遍历到t[1] = 'B'，此时j = nextval[0] = -1；
- t[j] = t[-1]，跳过此步骤，直接执行nextval[1] = 0；
- 遍历到t[2] = 'C'，此时j = nextval[1] = 0； -t[j]!=t[2]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行nextval[2] = 0； - 遍历到t[3] = 'D'，此时j = nextval[2] = 0； -t[j]!=t[3]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行nextval[3] = 0； - 遍历到t[4] = 'A'，此时j = nextval[3] = 0； -t[j]!=t[4]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行nextval[4] = 0； - 遍历到t[5] = 'B'，此时j = nextval[4] = 0； -t[j]!=t[5]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行nextval[5] = 0； - 遍历到t[6] = 'D'，此时j = nextval[5] = 0； -t[j]!=t[6]，需要继续向前回溯，因为j=0；
- t[j] = t[-1]，跳过此步骤，直接执行nextval[6] = 0； 所以模式串t的nextval数组为：[-1, 0, 0, 0, 0, 0, 0]。 通过计算next数组和nextval数组，可以在字符串匹配时加速匹配过程，提高匹配效率。
因篇幅问题不能全部显示，请点此查看更多更全内容