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

在c++的编程中，字符串匹配问题是十分常见的问题。简单来说，字符串匹配问题就是在文本串中查找特定的模式串的过程。在实际的应用中，字符串匹配算法主要用于文本搜索、图像识别和自然语言处理等领域。本篇文章将着重介绍c++中常用的字符串匹配算法及其实现。

1. 朴素字符串匹配算法

朴素字符串匹配算法也被称为暴力搜索匹配算法。其思路就是通过对文本串T的每个位置都依次尝试匹配模式串P，直到找到匹配的位置或者是整个T中不存在P为止。这种算法的时间复杂度较高，为O(n*m)，n和m分别是文本串T和模式串P的长度。

C++代码实现如下：

立即学习“C++免费学习笔记（深入）”；

MD5校验和计算小程序（C）

C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。

下载

void naive_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    for(int i = 0; i <= n-m; i++) {
        int j;
        for(j = 0; j < m; j++) {
            if(T[i+j] != P[j]) break;
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i << endl;
        }
    }
}

2. KMP字符串匹配算法

KMP字符串匹配算法是一种经典的字符串匹配算法，它的核心思想是通过对模式串P的前缀后缀的最长公共前缀后缀进行匹配，来避免在文本串T中对已经匹配过的字符进行重复匹配的过程。该算法的时间复杂度为O(n)，n为文本串的长度。

C++代码实现如下：

立即学习“C++免费学习笔记（深入）”；

void get_next(string P, vector& next) {
    int m = P.length();
    next[0] = -1;
    int i = 0;
    int j = -1;
    while(i < m) {
        if(j == -1 || P[i] == P[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void kmp_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector next(m+1);
    get_next(P, next);
    int i = 0;
    int j = 0;
    while(i < n) {
        if(j == -1 || T[i] == P[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i-m << endl;
            j = next[j];
        }
    }
}

3. BM字符串匹配算法

BM算法是一种基于坏字符和好后缀规则的字符串匹配算法。它的核心思想是通过对模式串P的最后一个字符进行匹配，并通过对文本串T中不匹配的字符进行预处理，来跳过已经匹配过的字符。该算法的时间复杂度为O(n)。

C++代码实现如下：

立即学习“C++免费学习笔记（深入）”；

const int MAXCHAR = 256;

void bm_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector badchar(MAXCHAR, -1);
    for(int i = 0; i < m; i++) {
        badchar[int(P[i])] = i;
    }
    vector suffix(m+1);
    vector prefix(m+1);
    get_suffix_prefix(P, suffix, prefix);
    int i = 0;
    while(i <= n-m) {
        int j = m-1;
        while(j >= 0 && P[j] == T[i+j]) j--;
        if(j < 0) {
            cout << "Pattern occurs with shift " << i << endl;
            i += (i+m < n) ? m-badchar[int(T[i+m])] : 1;
        } else {
            i += max(suffix[j+1], j-badchar[int(T[i+j])]);
        }
    }
}

本篇文章主要介绍了C++中常用的字符串匹配算法及其实现。朴素字符串匹配算法虽然简单，但时间复杂度较高，KMP和BM算法则能够更快速地找到匹配位置。其中，KMP算法适用于模式串较短，BM算法则适用于模式串较长的情况。在实际的应用中，我们需要根据不同的情况来选择合适的算法来进行字符串匹配。