C++字符串匹配算法详解（从暴力匹配到KMP算法的完整实现）

方法一：暴力匹配（Brute Force）

暴力匹配是最直观的方法：逐个字符比较，若不匹配则主串回退，模式串从头开始。虽然简单，但时间复杂度为 O(n×m)，效率较低。

#include <iostream>#include <string>// 暴力匹配算法int bruteForceSearch(const std::string& text, const std::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() {    std::string text = "ababcababa";    std::string pattern = "ababa";    int pos = bruteForceSearch(text, pattern);    if (pos != -1) {        std::cout << "匹配成功，起始位置: " << pos << std::endl;    } else {        std::cout << "未找到匹配" << std::endl;    }    return 0;}

方法二：KMP算法（Knuth-Morris-Pratt）

KMP算法通过预处理模式串，构建“部分匹配表”（也称 next 数组），避免主串指针回退，将时间复杂度优化至 O(n + m)。这是模式匹配C++中最经典且高效的算法之一。

步骤1：构建 next 数组

next[i] 表示 pattern[0..i] 的最长相等前后缀长度。例如，模式 "ABABC" 的 next 数组为 [0, 0, 1, 2, 0]。

void computeLPSArray(const std::string& pattern, std::vector<int>& lps) {    int m = pattern.length();    int len = 0; // 当前最长前缀后缀长度    lps[0] = 0; // 第一个字符没有真前缀    int i = 1;        while (i < m) {        if (pattern[i] == pattern[len]) {            len++;            lps[i] = len;            i++;        } else {            if (len != 0) {                len = lps[len - 1];            } else {                lps[i] = 0;                i++;            }        }    }}

步骤2：使用 next 数组进行匹配

int kmpSearch(const std::string& text, const std::string& pattern) {    int n = text.length();    int m = pattern.length();        if (m == 0) return 0;        std::vector<int> lps(m, 0);    computeLPSArray(pattern, lps);        int i = 0; // text 的索引    int j = 0; // pattern 的索引        while (i < n) {        if (pattern[j] == text[i]) {            i++;            j++;        }                if (j == m) {            return i - j; // 找到匹配        } else if (i < n && pattern[j] != text[i]) {            if (j != 0) {                j = lps[j - 1];            } else {                i++;            }        }    }    return -1; // 未找到}

为什么选择KMP？

相比暴力法，KMP在处理大量重复字符或长文本时优势明显。例如在 DNA 序列分析或日志检索中，字符串搜索算法的效率直接决定系统性能。KMP通过“跳过已知匹配部分”，大幅减少不必要的比较。

总结

本文从零开始讲解了 C++ 中两种核心的字符串匹配方法：暴力匹配适合初学者理解逻辑，而 KMP 算法则展示了如何通过预处理提升效率。掌握这些C++字符串匹配算法不仅有助于面试准备，更能提升你在实际项目中的编码能力。

建议你动手实现上述代码，并尝试用不同测试用例验证结果。随着练习深入，你会发现KMP算法实现其实并不神秘，而是巧妙利用了字符串自身的结构特性。