c++实现kmp算法

KMP算法是一种字符串匹配算法，它的时间复杂度为O(m+n)，其中m和n分别为模式串和匹配串的长度。KMP算法的核心思想是利用已知信息，尽可能减少无效的比较次数。

C++实现KMP算法的关键在于构建next数组，该数组表示当匹配失败时，下一次从哪个位置开始继续匹配。以下是KMP算法的C++实现：

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

void getNext(char *pattern, int next[]) {
    int n = strlen(pattern);
    next = -1;
    int k = -1;
    for (int i = 1; i < n; i++) {
        while (k != -1 && pattern[k+1] != pattern[i]) {
            k = next[k];
        }
        if (pattern[k+1] == pattern[i]) {
            k++;
        }
        next[i] = k;
    }
}

void KMP(char *text, char *pattern) {
    int m = strlen(text), n = strlen(pattern);
    int next[n];
    getNext(pattern, next);
    int j = -1;
    for (int i = 0; i < m; i++) {
        while (j != -1 && pattern[j+1] != text[i]) {
            j = next[j];
        }
        if (pattern[j+1] == text[i]) {
            j++;
        }
        if (j == n-1) {
            cout << "Pattern found at index " << i-n+1 << endl;
            j = next[j];
        }
    }
}

int main() {
    char text[] = "ABABCABABCD";
    char pattern[] = "ABABCD";
    KMP(text, pattern);
    return 0;
}