c++KMP算法典型案例代码并输出

KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，它可以在O(n+m)的时间复杂度内完成对字符串的匹配（其中n为文本字符串长度，m为模式字符串长度）。KMP算法的核心在于一个预处理过程，通过这个过程构建一个部分匹配表（也称为“失败函数”或“next数组”），用以在不匹配时跳过尽可能多的字符。

以下是一个典型的C++实现案例代码：

#include <iostream>
#include <vector>
#include <string>

// 构建部分匹配表（next数组）
std::vector<int> kmpNext(const std::string &pattern) {
    int m = pattern.length();
    std::vector<int> next(m, 0);
    int j = 0;

    // 计算next数组，该数组记录了模式串中前后缀的最长公共元素长度
    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        next[i] = j;
    }
    return next;
}

// KMP算法实现
void KMP(const std::string &text, const std::string &pattern) {
    int n = text.length();
    int m = pattern.length();
    std::vector<int> next = kmpNext(pattern);

    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            std::cout << "Pattern found at index " << i - j + 1 << std::endl;
            j = next[j - 1];
        }
    }
}

int main() {
    std::string text = "ABC ABCDAB ABCDABCDABDE";
    std::string pattern = "ABCDABD";
    KMP(text, pattern);
    return 0;
}

在这个代码中，首先通过`kmpNext`函数生成了模式字符串的next数组，然后在`KMP`函数中使用这个next数组来进行字符串匹配。如果找到匹配的子串，就会输出该子串在文本字符串中的起始索引位置。