C++字符串匹配算法详解（从暴力匹配到KMP高效模式匹配）

1. 什么是字符串匹配？

字符串匹配（String Matching），也称为模式匹配，是指在一个较长的字符串（称为主串或文本串）中查找一个较短的字符串（称为模式串或子串）是否出现，并返回其位置。

例如：
主串 S = "ABABDABACDABABCABCABCABC"
模式串 P = "ABABC"
我们要找出 P 在 S 中第一次出现的位置（从0开始计数）。

2. 暴力匹配算法（Brute Force）

暴力匹配是最直观的方法：逐个字符比较，若不匹配则主串回退，模式串重置。

#include <iostream>#include <string>using namespace std;// 暴力匹配算法int bruteForce(const string& text, const string& pattern) {    int n = text.length();    int m = pattern.length();        for (int i = 0; i <= n - m; ++i) {        int j = 0;        while (j < m && text[i + j] == pattern[j]) {            j++;        }        if (j == m) {            return i; // 找到匹配位置        }    }    return -1; // 未找到}int main() {    string text = "ABABDABACDABABCABCABCABC";    string pattern = "ABABC";    int pos = bruteForce(text, pattern);    if (pos != -1) {        cout << "匹配成功，位置: " << pos << endl;    } else {        cout << "未找到匹配" << endl;    }    return 0;}

暴力匹配的时间复杂度为 O(n×m)，在最坏情况下效率较低。例如当主串为 "AAAAA...AB"，模式串为 "AAAAB" 时，会进行大量重复比较。

3. KMP算法：高效避免回溯

KMP（Knuth-Morris-Pratt）算法通过预处理模式串，构建一个“部分匹配表”（也叫 next 数组），使得在匹配失败时，主串指针无需回退，从而将时间复杂度优化到 O(n + m)。

3.1 构建 next 数组

next[i] 表示模式串前 i 个字符中，最长相等前后缀的长度。

void computeNext(const string& pattern, vector<int>& next) {    int m = pattern.length();    next[0] = 0;    int j = 0; // 前缀末尾        for (int i = 1; i < m; ++i) {        while (j > 0 && pattern[i] != pattern[j]) {            j = next[j - 1];        }        if (pattern[i] == pattern[j]) {            j++;        }        next[i] = j;    }}

3.2 KMP匹配主函数

int kmpSearch(const string& text, const string& pattern) {    int n = text.length();    int m = pattern.length();        if (m == 0) return 0;        vector<int> next(m);    computeNext(pattern, next);        int j = 0; // 模式串指针    for (int i = 0; i < n; ++i) {        while (j > 0 && text[i] != pattern[j]) {            j = next[j - 1];        }        if (text[i] == pattern[j]) {            j++;        }        if (j == m) {            return i - m + 1; // 返回匹配起始位置        }    }    return -1;}

KMP算法的关键在于利用已匹配部分的信息，跳过不必要的比较。这正是C++字符串匹配算法中最具智慧的设计之一。

4. 总结

• 暴力匹配简单但效率低，适合小规模数据。
• KMP算法通过预处理实现线性时间复杂度，是工业级应用的首选。
• 理解模式匹配原理有助于掌握更高级的算法如Boyer-Moore、Rabin-Karp等。
• 在实际开发中，C++标准库的 string::find() 内部可能使用优化过的算法，但了解底层原理仍非常重要。

无论你是初学者还是进阶开发者，掌握这些字符串查找技巧都将大大提升你的编程能力。希望这篇教程能帮助你轻松入门C++字符串匹配算法！