串匹配kmp算法c++

KMP算法（Knuth-Morris-Pratt 算法）是一种高效的字符串匹配算法，它用于在一个主串中查找是否存在给定的模式串。该算法通过预处理模式串，创建一个部分匹配表（Partial Match Table，简称PMT），避免了无效的字符比较，提高了匹配效率。

以下是C++实现KMP算法的基本步骤：

1. **创建部分匹配表**：
- 对于模式串中的每个字符i，如果它的前缀和后缀相等，即`pattern[i] == pattern[j]`（其中`j`是之前已经匹配过的字符位置），那么`next[i] = j + 1`。
- 如果不相等，找到`next[j]`的位置，使得`0 <= next[j] < i`并且`pattern[next[j]+1...i]`和`pattern[0...j]`是相同的，然后设置`next[i] = next[j]`。

2. **主循环**：
- 比较主串和模式串的字符。
- 如果当前字符匹配，继续下一个。
- 如果不匹配，检查部分匹配表。如果主串当前字符对应的`next`值大于0，说明需要回退到上次正确的匹配位置继续比较；如果`next`值为0，表示未找到匹配，结束本次搜索。

下面是一个简单的C++ KMP算法实现示例：

#include <vector>
#include <string>

std::vector<int> get_next(const std::string& pattern) {
    int len = pattern.length();
    std::vector<int> next(len);
    for (int i = 1, j = 0; i < len; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        next[i] = j;
    }
    return next;
}

bool kmp_search(const std::string& text, const std::string& pattern) {
    std::vector<int> next = get_next(pattern);
    int pos = 0;
    for (char c : text) {
        while (pos > 0 && c != pattern[pos]) {
            pos = next[pos - 1];
        }
        if (c == pattern[pos]) {
            ++pos;
        }
        if (pos == pattern.length()) {
            return true;
        }
    }
    return false;
}