用C++实现KMP算法字符串的匹配

KMP（Knuth-Pratt）算法是一种用于字符串匹配的有效算法，它通过预处理模式串来避免在搜索过程中回溯。在C++中实现KMP算法，首先需要准备两个步骤：

1. **构建部分匹配表**（Partial Match Table, PMT）：
- 对于模式串，PMT记录的是当发生前缀与模式不匹配时，前缀最长公共前后缀的长度。例如，如果模式串是 "ababc"，PMT会是 [0, 0, 1, 2]，因为"aa"和"aba"都没有共同的前后缀，"abb"的最长公共前后缀是"a"，而"abc"的最长公共前后缀是"b".

2. **实际匹配过程**：
- 在目标串中从头开始匹配，每次遇到不匹配字符，利用PMT找到适当的偏移量，将模式串向右移动相应距离，直到找到匹配或超过目标串范围。

以下是简单的C++代码实现：

#include <vector>
#include <string>

std::vector<int> getPartialMatchTable(const std::string& pattern) {
    int n = pattern.size();
    std::vector<int> PMT(n);
    PMT[0] = -1;
    int len = 0; // 当前最长公共前后缀长度
    for (int i = 1; i < n; ++i) {
        while (len != 0 && pattern[i] != pattern[len]) {
            len = PMT[len - 1];
        }
        if (pattern[i] == pattern[len]) {
            ++len;
        }
        PMT[i] = len;
    }
    return PMT;
}

bool kmpMatch(const std::string& text, const std::string& pattern, int& matchedPos) {
    std::vector<int> PMT = getPartialMatchTable(pattern);
    int t = 0, p = 0;
    matchedPos = -1;

    while (t < text.size()) {
        if (text[t] == pattern[p]) {
            ++t;
            ++p;
        } else if (p != 0) {
            p = PMT[p - 1]; // 回溯到当前前后缀的下一个位置
        } else {
            ++t;
        }

        if (p == pattern.size()) {
            matchedPos = t - p; // 如果完全匹配，返回匹配的位置
            return true;
        }
    }
    return false;
}

在这个实现中，`kmpMatch`函数接受目标串`text`、模式串`pattern`以及一个引用变量`matchedPos`。它会在`text`中寻找`pattern`的第一个匹配位置，并更新`matchedPos`。