c++模式匹配算法理解

C++中的模式匹配算法主要有KMP算法和Boyer-Moore算法。其中KMP算法是一种比较常用的字符串匹配算法，其核心思想是利用已知信息避免重复匹配，从而提高匹配效率。

KMP算法的实现主要分为两个步骤：预处理和匹配。预处理阶段是为了计算出模式串中每个位置的最长前缀和最长后缀相等的长度，这个长度被称为“部分匹配值”，并存储在一个数组中。匹配阶段则是利用预处理阶段得到的部分匹配值进行匹配，如果匹配失败，则根据部分匹配值进行跳转，避免重复匹配。

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

#include <iostream>
#include <string>

using namespace std;

void get_next(string pattern, int next[]) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < pattern.size() - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmp(string text, string pattern) {
    int i = 0, j = 0;
    int next[pattern.size()];
    get_next(pattern, next);
    while (i < text.size() && j < pattern.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == pattern.size()) {
        return i - j;
    } else {
        return -1;
    }
}

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