位置：文档库 > C/C++ > C++中的字符串匹配算法及其实现

C++中的字符串匹配算法及其实现

络绎不绝上传于 2023-04-22 08:56

《C++中的字符串匹配算法及其实现》

字符串匹配是计算机科学中的基础问题，广泛应用于文本处理、搜索引擎、生物信息学等领域。在C++中，字符串匹配算法的效率直接影响程序性能，尤其是处理大规模文本时。本文将系统介绍C++中常见的字符串匹配算法，包括暴力匹配、KMP算法、Boyer-Moore算法和Rabin-Karp算法，并分析其实现原理与优化策略。

一、暴力匹配算法（Brute-Force）

暴力匹配算法是最直观的字符串匹配方法，其核心思想是通过逐个字符比较主串（文本串）和模式串，直到找到完全匹配或遍历完主串。

1.1 算法原理

设主串长度为n，模式串长度为m。算法从主串的第i个字符开始，与模式串的第j个字符逐一比较：

若字符匹配（S[i+j] == P[j]），则继续比较下一个字符；
若字符不匹配，则主串指针i后移一位，模式串指针j重置为0；
若j达到m，则匹配成功，返回起始位置i；
若i超过n-m，则匹配失败。

1.2 代码实现

#include 
#include 
using namespace std;

int bruteForce(const string& S, const string& P) {
    int n = S.length(), m = P.length();
    for (int i = 0; i

1.3 复杂度分析

时间复杂度：最坏情况下为O(n*m)，例如主串为"AAAAA"，模式串为"AAB"。空间复杂度为O(1)。

二、KMP算法

KMP算法通过预处理模式串，利用已匹配部分的信息避免不必要的回溯，将时间复杂度优化至O(n+m)。

2.1 部分匹配表（Partial Match Table）

部分匹配表（又称next数组）记录模式串中每个位置的最长相同前后缀长度。例如模式串"ABABC"的next数组为[-1, 0, 0, 1, 2]。

2.2 算法步骤

预处理模式串，构建next数组；
从主串和模式串的起始位置开始比较；
若字符匹配，则同时后移主串和模式串指针；
若字符不匹配，则根据next数组跳过已匹配部分。

2.3 代码实现

#include 
#include 
#include 
using namespace std;

vector buildNext(const string& P) {
    int m = P.length();
    vector next(m, 0);
    next[0] = -1;
    int i = 0, j = -1;
    while (i  next = buildNext(P);
    int i = 0, j = 0;
    while (i

2.4 复杂度分析

时间复杂度：预处理阶段O(m)，匹配阶段O(n)，总时间复杂度O(n+m)。空间复杂度O(m)（存储next数组）。

三、Boyer-Moore算法

Boyer-Moore算法通过从右向左比较模式串，利用坏字符规则和好后缀规则跳过不必要的比较，通常比KMP更快。

3.1 坏字符规则

当模式串与主串不匹配时，根据主串中不匹配的字符（坏字符）在模式串中的位置，移动模式串使坏字符对齐到模式串中最后一次出现的位置。

3.2 好后缀规则

若模式串中存在与已匹配部分相同的子串（好后缀），则移动模式串使该子串对齐。

3.3 代码实现

#include 
#include 
#include 
#include 
using namespace std;

vector buildBadChar(const string& P) {
    const int ALPHABET_SIZE = 256;
    vector badChar(ALPHABET_SIZE, -1);
    for (int i = 0; i (P[i])] = i;
    }
    return badChar;
}

int boyerMoore(const string& S, const string& P) {
    int n = S.length(), m = P.length();
    if (m == 0) return 0;
    vector badChar = buildBadChar(P);
    int s = 0;
    while (s = 0 && P[j] == S[s + j]) --j;
        if (j (S[s + j])];
            s += max(1, bcShift);
        }
    }
    return -1;
}

int main() {
    string text = "HERE IS A SIMPLE EXAMPLE";
    string pattern = "EXAMPLE";
    int pos = boyerMoore(text, pattern);
    if (pos != -1) cout

3.4 复杂度分析

时间复杂度：最好情况O(n/m)，最坏情况O(n*m)，平均情况接近O(n+m)。空间复杂度O(1)（仅坏字符规则）或O(m)（好后缀规则）。

四、Rabin-Karp算法

Rabin-Karp算法基于哈希函数，通过比较主串和模式串的哈希值快速筛选候选位置，再验证实际字符是否匹配。

4.1 滚动哈希

使用多项式滚动哈希计算子串的哈希值，例如：

H(s[i..i+m-1]) = (s[i]*d^(m-1) + s[i+1]*d^(m-2) + ... + s[i+m-1]) mod q

其中d为基数（如ASCII码数），q为大质数。

4.2 算法步骤

计算模式串的哈希值h_p；
计算主串前m个字符的哈希值h_s；
若h_p == h_s，则逐个字符验证；
若不匹配，则根据滚动哈希公式更新h_s，并比较下一个子串。

4.3 代码实现

#include 
#include 
using namespace std;

const int d = 256; // ASCII码数
const int q = 101; // 大质数

int rabinKarp(const string& S, const string& P) {
    int n = S.length(), m = P.length();
    if (m == 0 || n

4.4 复杂度分析

时间复杂度：平均情况O(n+m)，最坏情况O(n*m)（哈希冲突频繁）。空间复杂度O(1)。

五、算法选择与优化

1. 短模式串：暴力匹配或KMP；

2. 长模式串：Boyer-Moore或Rabin-Karp；

3. 内存敏感场景：优先选择空间复杂度低的算法（如Boyer-Moore仅坏字符规则）；

4. 多模式匹配：可结合AC自动机或后缀数组优化。

六、总结

C++中的字符串匹配算法各有优劣，暴力匹配简单但效率低，KMP通过预处理优化时间复杂度，Boyer-Moore利用启发式规则跳过比较，Rabin-Karp通过哈希快速筛选。实际应用中需根据数据规模、模式串长度和内存限制选择合适的算法。

关键词：字符串匹配算法、暴力匹配、KMP算法、Boyer-Moore算法、Rabin-Karp算法、C++实现、时间复杂度、空间复杂度、部分匹配表、坏字符规则、滚动哈希

简介：本文详细介绍了C++中四种主流字符串匹配算法（暴力匹配、KMP、Boyer-Moore、Rabin-Karp）的原理、实现代码与复杂度分析，并对比了不同场景下的算法选择策略，为开发者提供实用的字符串处理方案。

立即下载

C/C++相关