kmp算法c++

Sure! 这是 C++ 中的 KMP 算法实现：

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

using namespace std;

void buildNext(string pattern, vector<int>& next)
{
    int n = pattern.size();
    next[0] = -1;
    int j = -1;
    for (int i = 1; i < n; i++) {
        while (j >= 0 && pattern[i] != pattern[j + 1])
            j = next[j];
        if (pattern[i] == pattern[j + 1])
            j++;
        next[i] = j;
    }
}

int KMP(string text, string pattern)
{
    int n = text.size();
    int m = pattern.size();
    vector<int> next(m);
    buildNext(pattern, next);
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && text[i] != pattern[j + 1])
            j = next[j];
        if (text[i] == pattern[j + 1])
            j++;
        if (j == m - 1)
            return i - m + 1;
    }
    return -1;
}

int main()
{
    string text = "BBC ABCDAB ABCDABCDABDE";
    string pattern = "ABCDABD";
    int pos = KMP(text, pattern);
    if (pos == -1)
        cout << "The pattern is not found in the text." << endl;
    else
        cout << "The pattern is found at position " << pos << "." << endl;
    return 0;
}

其中 `buildNext` 函数用于构建 `next` 数组，`KMP` 函数使用 `next` 数组来匹配字符串。