如何用C++实现字符串中高效查找子串的功能？

在C++中，为了实现高效查找子串的功能，可以使用KMP算法（Knuth-Pratt算法）或Boyer-Moore算法，这两种算法都比朴素的线性搜索（逐字符比较）更快。这里简单介绍一下KMP算法：

**KMP算法步骤：**
1. **构建部分匹配表（Partial Match Table, PMT）**: 计算模式串前缀与后缀相等的最长长度，存储在一个数组`lps[]`中。这个过程从左到右遍历模式串，如果遇到之前已经计算过的前缀，就更新PMT。
2. **搜索主串**：对于每个位置`i`，检查`pattern[i]`是否等于`text[j]`（其中`j`是当前主串的位置）。如果不是，则移动`j`而不是`i`，因为PMT帮助我们避免了回溯。
- 如果相等，`i`、`j`都加一。
- 如果不相等，直接通过PMT找到下一个应该开始对比的位置`i + lps[i - pattern[i]]`。

**使用C++实现：**

#include <string>
#include <vector>

std::vector<int> getLPS(const std::string &pattern) {
    int len = 0, j = -1;
    std::vector<int> lps(pattern.size());
    for (int i = 1; i < pattern.size(); ++i) {
        while (j != -1 && pattern[i] != pattern[j + 1]) {
            j = lps[j];
        }
        if (pattern[i] == pattern[j + 1]) {
            j++;
        }
        lps[i] = j;
    }
    return lps;
}

bool KMP_search(const std::string &text, const std::string &pattern) {
    std::vector<int> lps = getLPS(pattern);
    int i = 0, j = 0;
    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            i++, j++;
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
        if (j == pattern.size()) {
            return true;
        }
    }
    return false;
}