求出模式串abaabcac的next值或nextval值

模式串"abaabcac"的next数组为:

|下标$i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:-----:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 字符串 | a | b | a | a | b | c | a | c |
| next值 | -1| 0 | 0 | 1 | 1 | 2 | 0 | 1 |

next数组的计算方法如下：

- 求出模式串中每个位置的前缀和后缀交集的最大长度，即以该位置为结尾的最长相同前缀和后缀的长度；
- 第一个位置的next值定义为-1；
- 从第二个位置开始，依次计算每个位置的next值，计算公式为：$next[i] = k$，其中$k$表示以第$i$个字符为结尾的最长相同前缀和后缀的长度，如果不存在这样的$k$，则令$next[i] = -1$。

对于模式串"abaabcac"，计算过程如下：

- $next[0] = -1$，因为第一个字符没有前缀和后缀；
- $next[1] = 0$，因为以第二个字符为结尾的最长相同前缀和后缀的长度为0；
- $next[2] = 0$，因为以第三个字符为结尾的最长相同前缀和后缀的长度为0；
- $next[3] = 1$，因为以第四个字符为结尾的最长相同前缀和后缀为"a"，长度为1；
- $next[4] = 1$，因为以第五个字符为结尾的最长相同前缀和后缀为"ab"，长度为1；
- $next[5] = 2$，因为以第六个字符为结尾的最长相同前缀和后缀为"abc"，长度为2；
- $next[6] = 0$，因为以第七个字符为结尾的最长相同前缀和后缀的长度为0；
- $next[7] = 1$，因为以第八个字符为结尾的最长相同前缀和后缀为"c"，长度为1。

因此，模式串"abaabcac"的next数组为$[-1, 0, 0, 1, 1, 2, 0, 1]$。

需要注意的是，next数组的计算方法是用于KMP算法中的，而nextval数组是用于BM算法中的，两者的计算方法有所不同。