C语言实现BM字符串匹配算法：从基础到实践

简介

在字符串处理领域，字符串匹配算法是一项核心技术。BM（Boyer-Moore）字符串匹配算法作为一种高效的字符串搜索算法，它的独特之处在于它从右向左进行字符比较，通过利用坏字符规则和好后缀规则，能够跳过大量不必要的比较，从而大大提高匹配效率。本文将详细介绍如何使用C语言实现BM字符串匹配算法，帮助读者深入理解并应用这一强大的算法。

目录

  1. 基础概念
    • 坏字符规则
    • 好后缀规则
  2. 使用方法
    • 预处理函数
    • 匹配函数
  3. 常见实践
    • 简单文本匹配
    • 文件内容搜索
  4. 最佳实践
    • 优化预处理
    • 减少内存使用
  5. 代码示例
  6. 小结
  7. 参考资料

基础概念

坏字符规则

在BM算法中，坏字符是指在文本串和模式串从右向左比较时，第一个不匹配的字符。当发现坏字符时，我们可以根据坏字符在模式串中最右出现的位置，将模式串向右移动一定的距离，使得坏字符对应的模式串位置能与文本串中的坏字符对齐（如果可能）。

好后缀规则

好后缀是指在文本串和模式串从右向左比较时，已经匹配的后缀部分。当出现不匹配时，根据好后缀在模式串中其他位置的出现情况，将模式串向右移动。好后缀规则比坏字符规则更为复杂，但它能提供更大的移动距离，进一步提高匹配效率。

使用方法

预处理函数

在进行实际匹配之前，我们需要对模式串进行预处理，构建坏字符表和好后缀表。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_CHAR 256

// 构建坏字符表
void buildBadCharTable(char *pattern, int badchar[MAX_CHAR]) {
    int len = strlen(pattern);
    for (int i = 0; i < MAX_CHAR; i++) {
        badchar[i] = -1;
    }
    for (int i = 0; i < len; i++) {
        badchar[(int)pattern[i]] = i;
    }
}

// 构建好后缀表（简化版本，仅展示思路）
void buildGoodSuffixTable(char *pattern, int *suffix, int *goodSuffix) {
    int m = strlen(pattern);
    int i, j;

    // 计算后缀数组
    for (i = 0; i < m; i++) {
        suffix[i] = 0;
    }
    for (i = m - 1; i >= 0; i--) {
        j = i;
        while (j >= 0 && pattern[j] == pattern[m - 1 - (i - j)]) {
            j--;
        }
        suffix[i] = i - j;
    }

    // 计算好后缀数组
    for (i = 0; i < m; i++) {
        goodSuffix[i] = m;
    }
    for (i = m - 1; i >= 0; i--) {
        if (suffix[i] == i + 1) {
            for (j = 0; j < m - 1 - i; j++) {
                if (goodSuffix[j] == m) {
                    goodSuffix[j] = m - 1 - i;
                }
            }
        }
    }
    for (i = 0; i <= m - 2; i++) {
        goodSuffix[m - 1 - suffix[i]] = m - 1 - i;
    }
}

匹配函数

使用预处理得到的坏字符表和好后缀表进行字符串匹配。

// BM字符串匹配函数
int boyerMoore(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int badchar[MAX_CHAR];
    int *suffix = (int *)malloc(m * sizeof(int));
    int *goodSuffix = (int *)malloc(m * sizeof(int));

    buildBadCharTable(pattern, badchar);
    buildGoodSuffixTable(pattern, suffix, goodSuffix);

    int s = 0;
    while (s <= n - m) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }
        if (j < 0) {
            free(suffix);
            free(goodSuffix);
            return s;
        } else {
            int x = j - badchar[(int)text[s + j]];
            int y = 0;
            if (j < m - 1) {
                y = goodSuffix[j + 1];
            }
            s += (x > y)? x : y;
        }
    }
    free(suffix);
    free(goodSuffix);
    return -1;
}

常见实践

简单文本匹配

在一段简单的文本中查找特定的模式串。

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    int result = boyerMoore(text, pattern);
    if (result!= -1) {
        printf("模式串在文本中出现的位置是: %d\n", result);
    } else {
        printf("模式串未在文本中找到\n");
    }
    return 0;
}

文件内容搜索

在一个文件中搜索特定的字符串。

int main() {
    FILE *file = fopen("example.txt", "r");
    if (file == NULL) {
        perror("无法打开文件");
        return 1;
    }

    char text[10000];
    fgets(text, sizeof(text), file);
    char pattern[] = "search_string";
    int result = boyerMoore(text, pattern);
    if (result!= -1) {
        printf("模式串在文件中出现的位置是: %d\n", result);
    } else {
        printf("模式串未在文件中找到\n");
    }

    fclose(file);
    return 0;
}

最佳实践

优化预处理

在构建坏字符表和好后缀表时，可以进一步优化算法的时间复杂度。例如，在构建好后缀表时，可以使用更高效的数据结构和算法，减少不必要的计算。

减少内存使用

在构建表的过程中，可以采用一些技巧来减少内存的占用。例如，对于坏字符表，可以使用稀疏数组来存储，只记录出现过的字符的位置。

小结

BM字符串匹配算法是一种高效的字符串匹配算法，通过坏字符规则和好后缀规则，能够显著提高匹配效率。本文详细介绍了BM算法的基础概念、使用方法、常见实践以及最佳实践，并提供了完整的C语言代码示例。希望读者通过阅读本文，能够深入理解并熟练应用BM字符串匹配算法。

参考资料