求解串′ababaaababaa′的next数组和nextval数组

串'ababaaababaa'的next数组为：-1 0 0 1 2 3 1 1 2 3 4 5

nextval数组可由next数组求得，具体求法如下：

string s = "ababaaababaa";
vector<int> next(s.size()), nextval(s.size());
next[0] = -1;
int j = -1;
for (int i = 1; i < s.size(); i++) {
    while (j != -1 && s[i] != s[j + 1]) {
        j = next[j];
    }
    if (s[i] == s[j + 1]) {
        j++;
    }
    next[i] = j;
}
for (int i = 0; i < s.size(); i++) {
    if (next[i] == -1 || s[i] != s[next[i]]) {
        nextval[i] = next[i];
    } else {
        nextval[i] = nextval[next[i]];
    }
}

其中，next数组的求解采用了KMP算法的思想，nextval数组的求解则是在next数组的基础上进行的。