kmp模式匹配算法的C++代码

KMP（Knuth-Pratt）算法是一种高效的字符串匹配算法，它通过构建部分匹配表（也称为失配函数）来避免回溯过程。以下是KMP算法的一个基本C++实现：

#include <iostream>
#include <vector>

// 失配函数，用于存储已经计算过的最长前后缀公共子串长度
std::vector<int> getPrefixFunction(const std::string& pattern) {
    int n = pattern.size();
    std::vector<int> prefix(n);
    for (int i = 1; i < n; ++i) {
        int j = prefix[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefix[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        prefix[i] = j;
    }
    return prefix;
}

// KMP搜索主函数
bool kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> prefix = getPrefixFunction(pattern);
    int index = 0;
    for (int i = 0; i < text.size(); ++i) {
        while (index > 0 && text[i] != pattern[index]) {
            index = prefix[index - 1];
        }
        if (text[i] == pattern[index]) {
            ++index;
        }
        if (index == pattern.size()) {
            std::cout << "Pattern found at position: " << i - index + 1 << "\n";
            index = prefix[index - 1]; // 如果找到，回到失配位置继续查找下一个位置
        }
    }
    return index == 0; // 没有找到则返回false
}

int main() {
    std::string text = "ABABCABAD";
    std::string pattern = "ABCA";
    if (kmpSearch(text, pattern)) {
        std::cout << "Pattern found.\n";
    } else {
        std::cout << "Pattern not found.\n";
    }
    return 0;
}

这个程序首先计算模式串的前缀函数，然后在文本串中使用该函数进行匹配。如果找到匹配，则会输出模式的位置，并从失配位置继续查找。