数据结构kmp的代码

KMP算法是一种字符串匹配算法，可以在O(n+m)的时间复杂度内找到一个字符串在另一个字符串中的所有出现位置。以下是KMP算法的代码实现：

#include <iostream>
#include <cstring>
using namespace std;

void getNext(string pattern, int* next) {
    int j = 0, k = -1;
    next[0] = -1;
    while (j < pattern.size() - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

void kmp(string text, string pattern) {
    int i = 0, j = 0;
    int* next = new int[pattern.size()];
    getNext(pattern, next);
    while (i < text.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if (j == pattern.size()) {
            cout << "Found pattern at index " << i - j << endl;
            j = next[j];
        }
    }
    delete[] next;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    kmp(text, pattern);
    return 0;
}