如何使用C++编程语言实现KMP（Knuth-Morris-Pratt）算法来处理字符串模式匹配，尤其是在手动输入字符串的情况下?

在C++中，通过实现KMP算法（Knuth-Morris-Pratt算法），你可以编写一个程序来自动检测给定的大字符串（主串）中是否包含了用户手动输入的小字符串（模式串）。以下是详细的步骤和代码实现：

首先，我们需要定义一个辅助函数`getPartialMatch`，用于生成部分匹配表，它描述了模式串中当前位置之前有多少次前缀与之后的剩余部分完全相同：

vector<int> getPartialMatch(const string& pattern) {
    int n = pattern.length();
    vector<int> partialMatch(n, 0);
    int j = 0; // 指向已经计算的部分匹配表元素
    for (int i = 1; i < n; ++i) {
        while (j > 0 && pattern[j] != pattern[i]) {
            j = partialMatch[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            ++j;
        }
        partialMatch[i] = j; // 更新当前位置的匹配长度
    }
    return partialMatch;
}

然后，在主函数中，接收用户输入的主串和模式串，并调用上述函数计算部分匹配表，接着进行实际的搜索：

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

int main() {
    std::string mainStr, pattern;
    
    // 手动输入主串和模式串
    std::cout << "请输入主串: ";
    getline(std::cin, mainStr);
    std::cout << "请输入模式串: ";
    getline(std::cin, pattern);

    // 计算部分匹配表
    auto partialMatch = getPartialMatch(pattern);

    // 使用部分匹配表进行KMP搜索
    bool found = kmpSearch(mainStr, pattern, partialMatch);
    if (found) {
        std::cout << "模式串在主串中找到了!\n";
    } else {
        std::cout << "模式串在主串中未找到.\n";
    }

    return 0;
}

// KMP搜索函数
bool kmpSearch(const std::string& mainStr, const std::string& pattern, const std::vector<int>& partialMatch) {
    int mainIndex = 0, patternIndex = 0;
    while (mainIndex < mainStr.size() && patternIndex < pattern.size()) {
        if (mainStr[mainIndex] == pattern[patternIndex]) {
            mainIndex++;
            patternIndex++;
        } else if (patternIndex > 0) {
            patternIndex = partialMatch[patternIndex - 1];
        } else {
            mainIndex++;
        }
        if (patternIndex == pattern.size()) {
            return true; // 找到了匹配
        }
    }
    return false; // 没有找到匹配
}

在这个例子中，用户会看到提示，输入他们想要查找的主串和模式串，然后程序将运行KMP算法来确定模式串是否存在于主串中。