next和nextval

next和nextval是在字符串匹配算法中常用的两个数组。

1. next数组：next数组是用来存储模式串中每个位置的最长公共前后缀长度的数组。它的作用是在匹配过程中，当出现不匹配的情况时，根据next数组的值来确定模式串的下一个比较位置。next数组的计算可以使用KMP算法来实现。

2. nextval数组：nextval数组是在KMP算法中的一个优化，用来存储模式串中每个位置的最长公共前后缀长度的数组。它的作用是在匹配过程中，当出现不匹配的情况时，根据nextval数组的值来确定模式串的下一个比较位置。nextval数组的计算可以使用KMP算法中的get_nextval函数来实现。

下面是get_nextval函数的实现代码：

void get_nextval(string p, vector<int> next, vector<int> &nextval) {
    nextval = next; // 赋值
    int j, k;
    for (j = 2; j < nextval.size(); j++) {
        k = nextval[j];
        while (p[j] == p[k]) {
            k = nextval[k];
            nextval[j] = k;
        }
    }
}