C语言Boyer-Moore算法如何高效实现字符串匹配？-C语言-盈思创科技

Boyer-Moore 算法是一种非常高效的字符串搜索算法，尤其是在“长文本搜索短模式”的场景下，它的平均性能通常优于朴素算法（逐个字符比较）和 KMP 算法，其高效性主要来源于两个核心思想：坏字符规则 和 好后缀规则。

（图片来源网络，侵删）

算法核心思想

想象一下，你在一段很长的文本（Text）中找一个较短的词（Pattern），朴素的做法是从左到右，将 Pattern 和 Text 的对应部分逐个字符比较。

Boyer-Moore 的聪明之处在于，它从右向左比较字符，如果在比较过程中发现不匹配的字符（称为“坏字符”），算法会利用这个信息“跳过”一大段文本,而不是像朴素算法那样只移动一位。

坏字符规则

这是 Boyer-Moore 最主要的规则。

比较方向：从 Pattern 的末尾开始，向左与 Text 中的对应字符进行比较。
匹配成功：如果所有字符都匹配,则找到了一个匹配项。
匹配失败：如果在 Pattern 的位置 j 处发现一个不匹配的字符 c（即 Text[i+j] != Pattern[j]）。
- 情况 A：如果这个坏字符 c 不出现在 Pattern 中，那么我们可以放心地将 Pattern 向右移动，使得 Pattern 的开头对准当前 Text 位置 i+j 的下一个字符，这样可以跳过整个 Pattern 长度的文本。
- 情况 B：如果这个坏字符 c 出现在 Pattern 中的某个位置 k（k < j），那么我们可以将 Pattern 向右移动，使得 Pattern 中最右边的那个 c 与 Text 中的坏字符 c 对齐。

坏字符规则可以总结为：skip = j - k，k 是坏字符 c 在 Pattern 中最右边的出现位置（如果不存在，k 设为 -1）。j 是当前在 Pattern 中的比较位置。

（图片来源网络，侵删）

好后缀规则

这个规则是坏字符规则的补充，用于处理坏字符规则可能导致的“向左回溯”问题,进一步优化性能。

比较方向：同样从右向左。
匹配成功：假设 Pattern 的最后 m 个字符已经成功匹配（m > 0）。
匹配失败：在匹配这 m 个字符之后，下一个字符（Text 中的字符）不匹配。
- 情况 A：Pattern 中存在一个子串与这 m 个字符组成的“好后缀”完全匹配，并且这个匹配子串的后面不是另一个相同的字符，那么我们可以将 Pattern 向右移动，使得这个匹配子串与“好后缀”对齐。
- 情况 B：好后缀”是 Pattern 的某个前缀，那么我们可以将 Pattern 向右移动，使得这个前缀与“好后缀”对齐。
- 情况 C：如果以上都不满足，说明 Pattern 中不包含这个“好后缀”，我们可以直接将 Pattern 向右移动，使得整个 Pattern 越过这个“好后缀”。

在实际实现中，为了高效计算好后缀规则的移动距离，通常会预先处理 Pattern，构建一个 suffix 数组和一个 prefix 布尔数组。

C 语言实现

下面是一个完整的 C 语言实现,包含了坏字符规则和好后缀规则的预处理函数以及主搜索函数。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 预处理坏字符规则，创建一个坏字符跳转表
// bc_table[character] 表示字符在模式串中最右边的位置
void preprocess_bad_char(const char *pattern, int pattern_len, int *bc_table) {
    // 初始化跳转表，所有字符的默认值为 -1
    for (int i = 0; i < 256; i++) {
        bc_table[i] = -1;
    }
    // 填充跳转表，记录每个字符在模式串中最右边的索引
    for (int i = 0; i < pattern_len; i++) {
        bc_table[(unsigned char)pattern[i]] = i;
    }
}
// 预处理后缀规则
// 1. 生成 suffix 数组
// suffix[i] = pattern_len - 1 - i, pattern[i...pattern_len-1] 是一个后缀
// 否则 suffix[i] 是模式串中与 pattern[i...pattern_len-1] 匹配的子串的起始位置
void preprocess_suffix(const char *pattern, int pattern_len, int *suffix) {
    // 初始化 suffix 数组
    for (int i = 0; i < pattern_len; i++) {
        suffix[i] = -1;
    }
    // 从后向前遍历模式串
    int f = 0; // 匹配的起始位置
    int g = pattern_len - 1; // 匹配的结束位置
    suffix[g] = pattern_len; // 最后一个字符的后缀长度为1，但这里我们存的是模式串长度
    for (int i = pattern_len - 2; i >= 0; i--) {
        if (i > g && suffix[i + pattern_len - 1 - f] < i - g) {
            suffix[i] = suffix[i + pattern_len - 1 - f];
        } else {
            if (i < g) {
                g = i;
            }
            f = i;
            while (g >= 0 && pattern[g] == pattern[g + pattern_len - 1 - f]) {
                g--;
            }
            suffix[i] = f - g;
        }
    }
}
// 预处理前缀规则
// prefix[i] 为 true pattern[0...i] 是 pattern 的某个后缀的前缀
void preprocess_prefix(const char *pattern, int pattern_len, bool *prefix) {
    // 初始化 prefix 数组
    for (int i = 0; i < pattern_len; i++) {
        prefix[i] = false;
    }
    for (int i = 0; i < pattern_len - 1; i++) {
        int j = 0;
        while (j <= i && pattern[j] == pattern[pattern_len - 1 - i + j]) {
            j++;
        }
        if (j == i + 1) {
            prefix[i] = true;
        }
    }
}
// Boyer-Moore 主搜索函数
void boyer_moore_search(const char *text, const char *pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);
    if (pattern_len == 0 || text_len < pattern_len) {
        return;
    }
    // 1. 预处理阶段
    int *bc_table = (int *)malloc(256 * sizeof(int));
    preprocess_bad_char(pattern, pattern_len, bc_table);
    int *suffix = (int *)malloc(pattern_len * sizeof(int));
    bool *prefix = (bool *)malloc(pattern_len * sizeof(bool));
    preprocess_suffix(pattern, pattern_len, suffix);
    preprocess_prefix(pattern, pattern_len, prefix);
    // 2. 搜索阶段
    int i = 0; // text 中的当前对齐位置
    while (i <= text_len - pattern_len) {
        int j;
        // 从右向左比较
        for (j = pattern_len - 1; j >= 0; j--) {
            if (text[i + j] != pattern[j]) {
                break; // 发现坏字符
            }
        }
        // j < 0，说明完全匹配
        if (j < 0) {
            printf("Found pattern at index %d\n", i);
            // 如果还想找下一个，根据坏字符规则移动
            // 这里简单移动一位以找到所有匹配
            i += (pattern_len > 1) ? (pattern_len - suffix[0]) : 1; 
        } else {
            // 2.1 计算坏字符规则的移动距离
            int bad_char_skip = j - bc_table[(unsigned char)text[i + j]];
            // 2.2 计算好后缀规则的移动距离
            int good_suffix_skip = 0;
            if (j < pattern_len - 1) { // 如果好后缀长度大于0
                if (suffix[j] != -1) { // 情况A: 好后缀在模式串中出现过
                    good_suffix_skip = pattern_len - 1 - j + suffix[j];
                } else { // 情况B/C: 检查好后缀是否是前缀
                    int k = j + 1;
                    while (k < pattern_len && !prefix[k]) {
                        k++;
                    }
                    if (k < pattern_len) {
                        good_suffix_skip = pattern_len - 1 - k + 1;
                    } else {
                        good_suffix_skip = pattern_len - 1 - j + 1;
                    }
                }
            }
            // 3. 取两种规则中移动距离较大的一个
            i += (bad_char_skip > good_suffix_skip) ? bad_char_skip : good_suffix_skip;
        }
    }
    // 释放内存
    free(bc_table);
    free(suffix);
    free(prefix);
}
int main() {
    const char *text = "HERE IS A SIMPLE EXAMPLE. THE SIMPLE EXAMPLE IS FOR BOYER-MOORE ALGORITHM.";
    const char *pattern = "EXAMPLE";
    printf("Text: %s\n", text);
    printf("Pattern: %s\n", pattern);
    boyer_moore_search(text, pattern);
    printf("\n--- Another example ---\n");
    const char *text2 = "ABAAABCDABCDABCEABCDABCEABDE";
    const char *pattern2 = "ABCEABD";
    printf("Text: %s\n", text2);
    printf("Pattern: %s\n", pattern2);
    boyer_moore_search(text2, pattern2);
    return 0;
}

代码解释

1 预处理函数

preprocess_bad_char:
（图片来源网络，侵删）
- 创建一个大小为 256 的整数数组 bc_table（假设是 ASCII 字符集）。
- 遍历 pattern，对于每个字符 pattern[i]，将 bc_table[pattern[i]] 的值更新为 i，这样，bc_table[c] 就存储了字符 c 在 pattern 中最右边的索引，如果字符不存在，其值保持为 -1。
preprocess_suffix 和 preprocess_prefix:
- 这两个函数是为了高效实现好后缀规则。
- suffix 数组：suffix[i] 存储 pattern[i...pattern_len-1] 这个子串（好后缀）在 pattern 中从右往左下一个出现的位置偏移量，这个实现比较复杂,核心思想是利用已经计算好的信息来推导当前信息。
- prefix 数组：prefix[i] 是一个布尔值，pattern 的前 i+1 个字符 (pattern[0...i]) 是 pattern 的某个后缀的前缀，则为 true，对于 pattern = "abab"，prefix[1] 为 true，因为 "ab" 是 "abab" 的后缀 "bab" 的前缀。

2 主搜索函数 `boyer_moore_search`

初始化: 获取 text 和 pattern 的长度,并分配内存给预处理表。
搜索循环:
- i 是 text 中 pattern 的当前对齐起始位置。
- 内层比较循环: 从 j = pattern_len - 1 开始，向左比较 text[i+j] 和 pattern[j]。
- 完全匹配 (j < 0): j 变为负数，说明所有字符都匹配了，打印匹配位置 i，为了继续寻找下一个匹配，我们需要移动 i,这里使用了好后缀规则的一种简化情况来移动。
- 不匹配 (j >= 0):
  - 坏字符移动: bad_char_skip = j - bc_table[text[i+j]]。bc_table 中没有这个字符，bc_table 的值是 -1，bad_char_skip 会变成 j + 1,这是一个安全的移动距离。
  - 好后缀移动:
    - 首先检查好后缀的长度是否大于0 (j < pattern_len - 1)。
    - suffix[j] 不为 -1，说明这个好后缀在 pattern 中其他地方出现过（情况A），移动距离为 pattern_len - 1 - j + suffix[j]。
    - suffix[j] 为 -1，则检查这个好后缀是否是 pattern 的某个前缀（情况B），如果是，移动距离为 pattern_len - 1 - k + 1，如果也不是（情况C），移动距离为 pattern_len - 1 - j + 1。
  - 选择最大移动: i += max(bad_char_skip, good_suffix_skip)，这是 Boyer-Moore 算法的精髓,选择能跳过最多字符的移动方式。

算法优缺点

优点

速度快：在平均情况下，时间复杂度可以达到 O(n/m)，n 是文本长度，m 是模式长度，这在实践中非常快，远超 KMP 的 O(n)。
实用性高：对于自然语言文本，字母表有限，且模式串中常有重复字符,坏字符规则能提供巨大的性能优势。

缺点

预处理开销：需要额外的空间和时间来构建 bc_table, suffix, 和 prefix 表，对于非常短的 pattern,这些开销可能抵消其搜索优势。
最坏情况：在最坏情况下（文本为 AAAA...，模式为 BAAA），算法的时间复杂度会退化到 *O(nm)**，与朴素算法相同,但这种情况在实际中很少见。

简化版本（仅坏字符规则）

对于很多应用场景，仅使用坏字符规则已经足够高效，并且实现起来简单得多,下面是一个仅使用坏字符规则的简化版本。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void preprocess_bad_char(const char *pattern, int pattern_len, int *bc_table) {
    for (int i = 0; i < 256; i++) {
        bc_table[i] = -1;
    }
    for (int i = 0; i < pattern_len; i++) {
        bc_table[(unsigned char)pattern[i]] = i;
    }
}
void boyer_moore_search_simple(const char *text, const char *pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);
    if (pattern_len == 0 || text_len < pattern_len) {
        return;
    }
    int *bc_table = (int *)malloc(256 * sizeof(int));
    preprocess_bad_char(pattern, pattern_len, bc_table);
    int i = 0;
    while (i <= text_len - pattern_len) {
        int j;
        for (j = pattern_len - 1; j >= 0; j--) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j < 0) {
            printf("Found pattern at index %d (Simple version)\n", i);
            i++; // 移动一位以查找下一个匹配
        } else {
            // 坏字符规则：移动距离为 j - bc_table[text[i+j]]
            // bc_table 中没有该字符，bc_table[text[i+j]] 为 -1，移动距离为 j+1
            int skip = j - bc_table[(unsigned char)text[i + j]];
            i += (skip > 0) ? skip : 1; // 确保至少移动一位
        }
    }
    free(bc_table);
}
int main() {
    const char *text = "HERE IS A SIMPLE EXAMPLE. THE SIMPLE EXAMPLE IS FOR BOYER-MOORE ALGORITHM.";
    const char *pattern = "EXAMPLE";
    printf("Text: %s\n", text);
    printf("Pattern: %s\n", pattern);
    boyer_moore_search_simple(text, pattern);
    return 0;
}

这个简化版本更容易理解,并且在很多实际应用中性能依然非常出色。

C语言Boyer-Moore算法如何高效实现字符串匹配？

算法核心思想

坏字符规则

好后缀规则

C 语言实现

代码解释

1 预处理函数

2 主搜索函数 `boyer_moore_search`

算法优缺点

优点

缺点

简化版本（仅坏字符规则）

相关文章

目录[+]

算法核心思想

坏字符规则

好后缀规则

C 语言实现

代码解释

1 预处理函数

2 主搜索函数 boyer_moore_search

算法优缺点

优点

缺点

简化版本（仅坏字符规则）

相关文章

目录[+]

2 主搜索函数 `boyer_moore_search`