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

什么是字符串匹配？

字符串匹配的目标是在一个较长的主串（text）中，查找一个较短的模式串（pattern）是否出现，并返回其位置。

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

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

最简单的方法是逐个字符比较。如果发现不匹配，就将模式串向右移动一位，重新开始比较。

#include <iostream>#include <string>using namespace std;// 暴力匹配算法int bruteForceSearch(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 = "ABABDABACDABABCABCABC";    string pattern = "ABABC";        int pos = bruteForceSearch(text, pattern);    if (pos != -1) {        cout << "Pattern found at index: " << pos << endl;    } else {        cout << "Pattern not found!" << endl;    }        return 0;}

暴力匹配的时间复杂度为 O(n×m)，在最坏情况下效率较低。接下来我们介绍更高效的 KMP算法。

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

KMP算法的核心思想是：当发生不匹配时，利用已匹配部分的信息，避免主串指针回退，从而提高效率。它通过预处理模式串，构建一个 next数组（也叫失败函数或部分匹配表）来实现这一点。

步骤1：构建next数组

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

void computeLPSArray(const string& pattern, vector<int>& lps) {    int m = pattern.length();    int len = 0; // 当前最长相等前后缀的长度    lps[0] = 0; // 第一个字符的next值为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 string& text, const string& pattern) {    int n = text.length();    int m = pattern.length();        vector<int> lps(m, 0);    computeLPSArray(pattern, lps);        int i = 0; // 主串索引    int j = 0; // 模式串索引        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示例代码

#include <iostream>#include <vector>#include <string>using namespace std;void computeLPSArray(const string& pattern, 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++;            }        }    }}int kmpSearch(const string& text, const string& pattern) {    int n = text.length();    int m = pattern.length();        vector<int> lps(m, 0);    computeLPSArray(pattern, lps);        int i = 0, j = 0;        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;}int main() {    string text = "ABABDABACDABABCABCABC";    string pattern = "ABABC";        int pos = kmpSearch(text, pattern);    if (pos != -1) {        cout << "Pattern found at index: " << pos << endl;    } else {        cout << "Pattern not found!" << endl;    }        return 0;}

KMP算法的时间复杂度为 O(n + m)，远优于暴力匹配，特别适合处理大文本。

总结

本文详细介绍了两种常见的C++字符串匹配算法：暴力匹配和KMP算法。我们不仅讲解了原理，还提供了完整的、可运行的C++编程入门教程代码。对于初学者来说，理解KMP的关键在于掌握next数组的构建逻辑。

掌握这些模式匹配C++教程中的技巧，不仅能提升你的算法能力，还能为后续学习更高级的字符串算法（如Boyer-Moore、Rabin-Karp等）打下坚实基础。如果你正在准备面试或参加算法竞赛，KMP算法C++实现绝对是必学内容！

提示：建议动手敲一遍代码，调试几次，你会对匹配过程有更直观的理解。