严慧敏数据结构kmp算法完整代码

KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。下面是KMP算法的完整代码示例：

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

// 构建next数组
void getNext(const string& pattern, vector<int>& next) {
    int n = pattern.size();
    next.resize(n);
    next = -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 m = text.size();
    int n = pattern.size();
    vector<int> next;
    getNext(pattern, next);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (j == -1 || text[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == n) {
        return i - j;  // 返回模式串在主串中的起始位置
    }
    return -1;  // 模式串不在主串中出现
}

int main() {
    string text = "ABCABCDABABCDABCDABDE";
    string pattern = "ABCDABD";
    int pos = kmp(text, pattern);
    if (pos != -1) {
        cout << "Pattern found at position: " << pos << endl;
    } else {
        cout << "Pattern not found." << endl;
    }
    return 0;
}