KMP算法中next值的计算完整代码

下面是KMP算法中next值的计算完整代码（C++实现）：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 计算模式串的next数组
void getNext(const string& pattern, vector<int>& next) {
    int n = pattern.size();
    next.resize(n);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            ++i;
            ++j;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

// KMP算法匹配文本串和模式串
int kmp(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> next;
    getNext(pattern, next);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            ++i;
            ++j;
        }
        else {
            j = next[j];
        }
    }
    if (j == m) {
        return i - m;
    }
    else {
        return -1;
    }
}

int main() {
    string text = "BBC ABCDAB ABCDABCDABDE";
    string pattern = "ABCDABD";
    int pos = kmp(text, pattern);
    if (pos == -1) {
        cout << "匹配失败" << endl;
    }
    else {
        cout << "匹配成功，位置为：" << pos << endl;
    }
    return 0;
}

在上面的代码中，我们使用了vector来存储next数组。函数getNext()用于计算模式串的next数组，函数kmp()用于匹配文本串和模式串。最后，我们在main()函数中对KMP算法进行测试。