kmp算法c++，输入主串和副串，输出进行了多少次字符比较

KMP（Knuth-Pratt）算法是一种用于字符串匹配的高效算法，尤其适用于在主串（文本串）中查找是否存在某个固定的模式串（副串）。它的核心思想是通过预处理副串构建一个部分匹配表（也称作失配函数），来避免不必要的字符比较。

在C++中实现KMP算法，你需要做以下几个步骤：

1. 定义部分匹配表，通常初始化为0，表示从头开始匹配都是成功的。
2. 对于每个字符在副串中的位置i，如果它等于主串当前字符，那么更新i；否则，检查部分匹配表，找到最长的前缀和后缀相等的子串长度，然后移动主串的位置。
3. 如果找到了副串，则记录下已经比较过的字符数，即为主串长度减去这个最长前缀后缀的长度加1。
4. 如果遍历完整个主串还没有找到副串，返回已比较过的字符数（就是主串长度）。

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

#include <iostream>
#include <vector>

int getPrefixFunction(const std::string& pattern) {
    int prefix[(pattern.size() + 1)];
    for (size_t i = 1; i < pattern.size(); ++i) {
        int j = prefix[i - 1];
        while (j > 0 && pattern[j] != pattern[i]) {
            j = prefix[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            j++;
        }
        prefix[i] = j;
    }
    return prefix[pattern.size()];
}

int KMP_search(const std::string& text, const std::string& pattern) {
    int prefix = getPrefixFunction(pattern);
    int index = 0;
    int comparisons = 0;
    for (size_t i = 0; i < text.size(); ++i) {
        if (index == pattern.size()) {
            break;
        }
        if (text[i] == pattern[index]) {
            index++;
        } else {
            if (index > 0) {
                index = prefix[index - 1];
            } else {
                comparisons++; // 比较了当前字符，但未匹配
            }
        }
        comparisons++; // 总共比较次数
    }
    return comparisons;
}

int main() {
    std::string text = "ABABCAB";
    std::string pattern = "ABC";
    int comparisons = KMP_search(text, pattern);
    std::cout << "进行了 " << comparisons << " 次字符比较." << std::endl;
    return 0;
}

在这个例子中，如果你运行这个程序，它会在主串`ABABCAB`中找到第一个"ABC"，并输出进行的字符比较次数。