用C++实现数据结构算法4.3用KMP算法计算函数值例题abbabcac的代码

在C++中，KMP算法（Knuth-Morris-Pratt 算法）通常用于字符串匹配问题，包括计算某个模式串在主串中的位置。针对4.3节的例题"abbabcac"，我们首先要创建一个next数组存储前缀函数的结果，然后遍历主串查找模式串。以下是一个简单的C++代码实现：

#include <iostream>
#include <vector>

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

// KMP匹配主串
int kmp_search(const std::string& main_str, const std::string& pattern) {
    int len_main = main_str.length(), len_pattern = pattern.length();
    std::vector<int> next = get_next(pattern);
    int index = 0, j = 0;

    while (index < len_main) {
        if (main_str[index] == pattern[j]) {
            index++, j++;
        } else if (j != 0) {
            j = next[j - 1]; // 如果当前字符不匹配，回溯到next[j - 1]
        } else {
            index++; // 主串继续匹配下一个字符
        }
        if (j == len_pattern) { // 找到了匹配的模式
            return index - j;
        }
    }

    return -1; // 没有找到匹配
}

int main() {
    std::string main_str = "abbabcac";
    std::string pattern = "abc";
    int result = kmp_search(main_str, pattern);
    if (result != -1) {
        std::cout << "Pattern found at position " << result << std::endl;
    } else {
        std::cout << "Pattern not found" << std::endl;
    }
    return 0;
}

在这个例子中，`kmp_search` 函数首先计算了 `pattern` 的前缀函数 `next`，然后遍历 `main_str` 通过比较和回溯操作寻找 `pattern`。如果找到匹配，返回开始位置；否则返回 -1 表示未找到。