使用C/C++语言帮我写一个KMP算法

KMP算法是一种用于字符串匹配的有效算法，它通过构建部分匹配表（也称作失配函数）避免了回溯过程。以下是使用C++编写的基本KMP算法：

#include <string>
#include <vector>

// KMP表构造函数
std::vector<int> computeKMPSuffixArray(const std::string& pattern) {
    int n = pattern.length();
    std::vector<int> lps(n, 0);
    
    for (int i = 1; i < n; ++i) {
        int j = lps[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = lps[j - 1];
        }
        
        if (pattern[i] == pattern[j]) {
            lps[i] = j + 1;
        } else {
            lps[i] = 0;
        }
    }

    return lps;
}

// 主KMP搜索函数
bool kmpSearch(const std::string& text, const std::string& pattern, const std::vector<int>& lps) {
    int n = text.length(), m = pattern.length();
    int index = 0;

    for (int i = 0; i < n; ++i) {
        if (text[i] == pattern[index]) {
            index++;
        }
        if (index == m) { // 找到匹配
            std::cout << "Pattern found at index: " << i - m + 1 << std::endl;
            index = lps[index - 1]; // 如果当前字符失败，回退到lps对应的位置
        } else if (i > 0 && index > 0 && text[i] != pattern[index]) {
            index = lps[index - 1]; // 直接跳过已经匹配过的部分
        }
    }

    return index == 0; // 没有找到匹配时返回false
}

int main() {
    std::string text = "ABABCABAA";
    std::string pattern = "ABCA";
    std::vector<int> lps = computeKMPSuffixArray(pattern);

    if (kmpSearch(text, pattern, lps)) {
        std::cout << "Match found." << std::endl;
    } else {
        std::cout << "No match found." << std::endl;
    }

    return 0;
}

这个程序首先计算了模式串`pattern`的部分匹配表(lps)，然后在文本串`text`中查找是否存在该模式。如果找到匹配，就会打印出匹配的位置。