KMP算法的next数组代码实现

KMP算法（Knuth-Morris-Pratt 算法），用于解决字符串匹配问题，通过预处理模式串，避免了不必要的回溯操作。核心是构建了一个next数组，它记录了模式串中每个位置到失配字符的最远距离。下面是next数组的一个基本的C++代码实现：

#include <vector>

void computeNext(std::string pattern, std::vector<int>& next) {
    int j = -1; // last matched character's index
    next = -1;
    for (int i = 1; i < pattern.length(); ++i) {
        while (j != -1 && pattern[j + 1] != pattern[i]) {
            j = next[j];
        }
        if (pattern[j + 1] == pattern[i]) {
            ++j;
        }
        next[i] = j;
    }
}

// 使用next数组在主字符串中查找模式
bool kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> next(pattern.size());
    computeNext(pattern, next);
    int i = 0, j = 0;
    while (i < text.length()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else if (j != -1) {
            j = next[j];
        } else {
            i++;
        }
        if (j == pattern.size()) {
            return true; // pattern found
        }
    }
    return false; // pattern not found
}

在这个实现中，`computeNext`函数计算next数组，然后`kmpSearch`函数利用next数组进行字符串匹配。