如何实现C++中的字符串匹配算法？多种经典方案详解与性能对比

字符串匹配要解决的核心问题很明确：给定一个主串S和一个模式串P，找出P在S中首次出现的位置，或者统计出现的次数。这个问题看似简单，但不同解法之间的性能差距可以达到数量级。比如在一个100万字符的文本里查找一个1000字符的模式串，暴力法可能需要上亿次字符比较，而KMP算法只需要线性时间。下面我们从最直观的方案入手，逐层深入。

一、从BF暴力匹配说起：最直观但最慢的方案

BF算法（Brute Force，暴力匹配）是所有人都能第一时间想到的方案：从主串的第一个字符开始，与模式串逐个比较；如果某个位置不匹配，主串指针回退到起始位置的下一个字符，模式串指针归零，重新开始比较。这个思路完全符合直觉，代码也非常短。

#include <iostream>
#include <string>

// BF暴力匹配，返回模式串在主串中首次出现的下标，找不到返回-1
int bfSearch(const std::string& s, const std::string& p) {
    int n = s.size(), m = p.size();
    if (m == 0) return 0;
    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && s[i + j] == p[j]) {
            ++j;
        }
        if (j == m) return i; // 完全匹配成功
    }
    return -1;
}

int main() {
    std::string s = "abcabcabcdabcde";
    std::string p = "abcd";
    std::cout << "匹配位置: " << bfSearch(s, p) << std::endl; // 输出 6
    return 0;
}

BF算法的问题在于主串指针会不断回退。最坏情况下（比如主串是aaaa...a，模式串是aaab），每次比较都要到最后一个字符才失败，时间复杂度退化为O(n*m)，其中n是主串长度，m是模式串长度。当n达到百万级别、m达到几千时，性能开销就很难接受了。

不过BF算法并非一无是处。在模式串很短（比如几个字符）、主串不长的日常场景下，它的常数因子小，实际表现往往不差。C++标准库中std::string::find在多数实现里采用的也是类似朴素匹配的思路（部分实现做了小优化），日常业务代码中直接用它就足够了：

std::string text = "hello world, hello c++";
size_t pos = text.find("hello");
if (pos != std::string::npos) {
    std::cout << "找到位置: " << pos << std::endl;
}

二、KMP算法：用next数组避免主串指针回退

KMP算法的核心思想是：当匹配失败时，利用已经比较过的信息，让主串指针不回退，只移动模式串。要做到这一点，关键在于预处理出一个next数组（也叫失败指针或部分匹配表），它记录了模式串每个位置之前的前缀子串中，最长相等前后缀的长度。

举个例子，模式串ABABC在位置4（字符C）失配时，前面已经匹配的部分是ABAB。这个子串最长相等的前后缀是AB（长度为2），说明模式串开头两个字符AB与已匹配部分的末尾两个字符AB相同，因此模式串可以直接滑动到让前缀AB对齐主串当前位置，中间的部分不可能匹配，无需再比较。这就是next数组省时间的本质：它跳过了所有注定失败的比较。

求解next数组的过程，本质上模式串自己和自己做匹配，代码是典型的动态规划写法：

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

// 构造next数组，next[i]表示p[0..i]中最长相等前后缀的长度
std::vector<int> buildNext(const std::string& p) {
    int m = p.size();
    std::vector<int> next(m, 0);
    int k = 0; // 当前最长相等前后缀长度
    for (int i = 1; i < m; ++i) {
        while (k > 0 && p[i] != p[k]) {
            k = next[k - 1]; // 失配时回退到更短的前后缀
        }
        if (p[i] == p[k]) {
            ++k;
        }
        next[i] = k;
    }
    return next;
}

// KMP主匹配过程，主串指针i永不回退
int kmpSearch(const std::string& s, const std::string& p) {
    int n = s.size(), m = p.size();
    if (m == 0) return 0;
    std::vector<int> next = buildNext(p);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1]; // 模式串滑动，主串不动
        }
        if (s[i] == p[j]) {
            ++j;
        }
        if (j == m) {
            return i - m + 1; // 返回匹配起点
        }
    }
    return -1;
}

int main() {
    std::string s = "ABABDABACDABABCABAB";
    std::string p = "ABABCABAB";
    std::cout << "匹配位置: " << kmpSearch(s, p) << std::endl; // 输出 10
    return 0;
}

这段代码里最容易混淆的是k = next[k - 1]这一行。它表示当前长度为k的前后缀无法继续延长时，退而求其次，尝试更短的相等前后缀。可以把next数组想象成一条链表：每次失配就沿着链往回跳，直到找到能继续匹配的前缀或者退到起点。理解了这一点，KMP就不再神秘。

KMP的时间复杂度是O(n + m)：预处理next数组需要O(m)，匹配过程虽然有两层循环，但主串指针只前进不后退，模式串指针的回退总量不超过其前进总量，整体仍是线性。代价是需要额外O(m)的空间，以及代码比BF复杂不少。如果需要统计模式串出现的所有位置，只需在j == m时记录i - m + 1，再执行j = next[j - 1]继续匹配即可。

三、Boyer-Moore-Horspool与 Sunday算法：跳着比较更快

除了KMP这类前缀匹配思路，还有一类后缀匹配算法，代表是Boyer-Moore及其简化版Horspool。它们的策略正好相反：从模式串的末尾开始比较，并且根据失配时主串中某个字符的信息，决定模式串可以一次性跳过多少个位置。在模式串较长、字符集较大的场景（比如自然语言文本搜索）下，这类算法的实际比较次数往往远少于KMP。

Horspool算法的规则很简单：每次对齐后，看主串中与模式串末尾对齐的那个字符c。如果c在模式串中出现过，就把模式串滑动到最右边出现的c与主串中的c对齐；如果没出现，直接滑动整个模式串长度加一。预处理阶段为每个可能出现的字符计算滑动距离即可：

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

// Horspool算法，用滑动表加速匹配
int horspoolSearch(const std::string& s, const std::string& p) {
    int n = s.size(), m = p.size();
    if (m == 0) return 0;
    if (m > n) return -1;

    // 预处理：默认滑动m，字符出现则滑动到最右出现位置的距离
    std::vector<int> shift(256, m);
    for (int i = 0; i < m - 1; ++i) {
        shift[(unsigned char)p[i]] = m - 1 - i;
    }

    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        // 从右向左比较
        while (j >= 0 && s[i + j] == p[j]) {
            --j;
        }
        if (j < 0) return i; // 全部匹配成功
        i += shift[(unsigned char)s[i + m - 1]]; // 按表滑动
    }
    return -1;
}

int main() {
    std::string s = "a simple example for horspool matching";
    std::string p = "example";
    std::cout << "匹配位置: " << horspoolSearch(s, p) << std::endl;
    return 0;
}

Horspool的平均时间复杂度约为O(n)，最好情况下可以达到O(n/m)——每次失配直接跳过整个模式串长度，这比KMP的逐字符推进快得多。它的劣势在最坏情况依然是O(n*m)，不过在真实文本上这种极端情况极少出现。

还有一个值得关注的变体是Sunday算法，它与Horspool思路接近，但考察的是对齐窗口后紧跟的那个字符，滑动距离通常更大，实践中经常是这几者里最快的一个。此外，如果需要在一个固定文本中反复查询多个不同的模式串，就应该考虑Aho-Corasick自动机（AC自动机），它把多个模式串构建成Trie树并添加失配指针，可以一次扫描同时完成所有模式串的匹配，是多模式匹配的标准解法。

四、如何选择：场景决定方案

没有万能的最优算法，选择时可以参考下面的对比表：

给几条实操建议：第一，写业务代码时优先用std::string::find或者std::search，标准库实现经过优化，代码可读性也最好；第二，处理流式数据（比如网络包解析）时KMP更合适，因为它的主串指针不回退，天然支持单遍扫描；第三，做文本编辑器的查找功能、日志关键字扫描这类模式串固定且较长的任务，Horspool或Sunday的实际速度通常最快；第四，涉及敏感词过滤、入侵检测这类需要同时匹配成百上千个关键词的场景，直接上AC自动机。

最后提醒一点性能测试中的坑：测试字符串匹配算法时，不要只用随机字符串，一定要加入刻意构造的坏用例（如全a主串配aaab模式串），否则BF和KMP的差距可能完全体现不出来。同时记得开启编译器优化（如-O2），否则测试结果反映的是未优化代码的表现，参考价值有限。理解每种算法的失配处理策略，比背下代码本身更重要——这才是解决各类字符串问题的通用钥匙。

C++字符串匹配KMP算法BF算法修改时间：2026-09-14 13:59:31