BM算法详解（C语言实现高效字符串匹配）

为什么选择BM算法？

在实际应用中，BM算法的平均时间复杂度接近 O(n/m)（其中 n 是主串长度，m 是模式串长度），远优于朴素算法的 O(n×m)。尤其当模式串较长时，BM算法的优势更加明显。这也是为什么许多高性能文本处理工具（如 grep）内部使用了BM或其变种。

核心思想：坏字符规则

假设我们在主串中从右向左比对模式串。如果发现某个字符不匹配（称为“坏字符”），我们可以根据该坏字符在模式串中的位置，决定向右滑动多少位。

例如：

• 主串：... A B C D ...
• 模式串：X Y Z

当比对到 Z 和 A 不匹配时，A 就是坏字符。我们查看 A 是否出现在模式串中。如果没有，则整个模式串可以直接跳过当前对齐位置；如果有，则对齐到模式串中最右边出现的 A 的位置。

C语言实现步骤

为了简化，我们先只实现坏字符规则。完整的BM算法还需结合好后缀规则，但仅坏字符规则已能大幅提升性能。

1. 构建坏字符表

我们需要一个数组 badChar，记录每个字符在模式串中最后一次出现的位置（从0开始）。未出现的字符默认为 -1。

void buildBadCharTable(char* pattern, int patLen, int badChar[256]) {    // 初始化所有字符为 -1    for (int i = 0; i < 256; i++) {        badChar[i] = -1;    }    // 记录每个字符最后出现的位置    for (int i = 0; i < patLen; i++) {        badChar[(unsigned char)pattern[i]] = i;    }}

2. BM匹配主函数

int boyerMooreSearch(char* text, char* pattern) {    int textLen = strlen(text);    int patLen = strlen(pattern);        if (patLen == 0) return 0;    if (textLen < patLen) return -1;        int badChar[256];    buildBadCharTable(pattern, patLen, badChar);        int shift = 0; // 当前模式串相对于主串的偏移        while (shift <= (textLen - patLen)) {        int j = patLen - 1; // 从模式串末尾开始比对                // 从右向左比对        while (j >= 0 && pattern[j] == text[shift + j]) {            j--;        }                if (j < 0) {            // 找到匹配            return shift; // 返回起始位置        } else {            // 计算滑动距离            int badCharShift = j - badChar[(unsigned char)text[shift + j]];            shift += (badCharShift > 0) ? badCharShift : 1;        }    }        return -1; // 未找到}

3. 完整测试代码

#include <stdio.h>#include <string.h>// 上面两个函数定义放在这里...int main() {    char text[] = "ABAAABCDABCABC";    char pattern[] = "ABC";        int pos = boyerMooreSearch(text, pattern);        if (pos != -1) {        printf("Pattern found at index %d\n", pos);    } else {        printf("Pattern not found\n");    }        return 0;}

总结

通过本教程，你已经掌握了BM算法的基本原理和C语言字符串匹配的实现方法。虽然我们只实现了坏字符规则，但这足以应对大多数场景。若想进一步优化，可研究好后缀规则，构建更复杂的跳转表。

记住，BM算法的核心优势在于：越长的模式串，跳得越远，效率越高。这也是它成为工业级字符串搜索首选算法的原因之一。

希望这篇教程能帮助你理解高效字符串搜索的奥秘！动手试试吧，编程的乐趣在于实践。