数据结构中求next数组的代码

在数据结构中，尤其是处理字符串、链表等动态数据的情况时，"next array"通常是指前缀或后缀数组，用于快速查找某个子串在原串中的起始位置。这里以字符串为例，假设我们有一个字符串S，创建next数组的目标是在常数时间内找到子串S[i..j]在S中的起始位置。

例如对于C++，我们可以用KMP算法生成next数组：

#include <vector>
#include <string>

std::vector<int> getNext(const std::string &s) {
    int n = s.size();
    std::vector<int> next(n);
    int j = -1;
    
    for (int i = 1; i < n; ++i) {
        while (j != -1 && s[i] != s[j + 1]) {
            j = next[j];
        }
        
        if (s[i] == s[j + 1]) {
            ++j;
        }
        
        next[i] = j;
    }
    
    return next;
}

这段代码首先初始化`next[0] = -1`，然后从第二个字符开始遍历字符串，通过维护两个指针i和j，如果当前字符匹配，就移动j；如果不匹配，则尝试跳过已经匹配的部分，即移动j到下一个next[j]的位置。这样最后得到的next数组就能满足KMP算法的要求。