c语言boyermoore-C语言-盈思创科技

Boyer-Moore 是一种非常高效的字符串搜索算法，尤其当“模式串”（Pattern）比“文本串”（Text）短很多时，它的性能往往优于朴素算法和 KMP 算法，其高效的核心在于它采用了两种启发式规则，允许算法在匹配失败时一次性跳过多个字符，而不是像 KMP 那样只能移动一个。

Boyer-Moore 算法核心思想

想象一下,你在字典里找一个单词，你不会一个字母一个字母地比对，你可能会先看第一个字母，然后快速翻页，直到找到以该字母开头的单词区域，Boyer-Moore 算法借鉴了这种思想。

算法从文本串的末尾开始,反向与模式串进行比较，主要有两种“坏字符”和“好后缀”规则来决定下一次匹配的起始位置。

坏字符规则

这是最直观的规则。

匹配过程：从模式串的末尾开始，向前与文本串的对应字符进行比较。
遇到坏字符：如果在某个位置，文本串中的字符 T[k] 与模式串中的字符 P[j] 不匹配，T[k] 就是一个“坏字符”。
跳转策略：
- 在模式串中查找这个坏字符 T[k] 出现的位置。
- 如果找到了,就将模式串向右移动，使得模式串中找到的这个 T[k] 与文本串中的 T[k] 对齐。
- 如果模式串中不存在这个坏字符,就直接将整个模式串移动到坏字符的右边。

示例:

文本串: HERE IS A SIMPLE EXAMPLE
模式串: EXAMPLE

当匹配到 SIMPLE 和 EXAMPLE 时，会在 'I' 和 'X' 处不匹配。'X' 是坏字符，我们在模式串 EXAMPLE 中查找 'X'，发现没有，我们可以将模式串直接向右移动，让 'X' 落在模式串之外，即移动 7 位。

HERE IS A SIMPLE EXAMPLE
      EXAMPLE  <-- 失败于 'X' vs 'I'
           EXAMPLE  <-- 直接跳过 'X' 的位置

好后缀规则

这个规则比坏字符规则更复杂,但也更强大，它利用了已经成功匹配的部分信息。

匹配过程：同样是从后往前匹配。
遇到好后缀：假设模式串 P 的最后 k 个字符已经成功匹配了文本串 T 的对应部分，但前面的字符 P[j] 与 T[i] 不匹配，这 k 个字符就是“好后缀”。
跳转策略：
- 情况一：在模式串 P 中，查找这个“好后缀”在 P 中前面出现的位置，如果找到了，就将模式串向右移动，使得这个前面的子串与文本串中的“好后缀”对齐。
- 情况二：好后缀”在模式串 P 的前面没有出现过，就在 P 的前缀中寻找一个最长后缀，这个后缀是“好后缀”的一个前缀，然后将模式串移动，使得这个匹配的前缀与文本串中的“好后缀”对齐。

示例:

文本串: ABABDABACDABABCABAB
模式串: ABABCABAB

当匹配到 ABABDABACDABABCABAB 和 ABABCABAB 时，会在 'D' 和 'C' 处不匹配，已经成功匹配了“好后缀” ABAB。

我们在模式串 ABABCABAB 的前面查找 ABAB，它出现在 P[0..3]。
我们将模式串向右移动,使得 P[0..3] 的 ABAB 与文本串中的 ABAB 对齐。

ABABDABACDABABCABAB
    ABABCABAB  <-- 失败于 'D' vs 'C', 好后缀是 'ABAB'
        ABABCABAB  <-- 移动，使模式串前面的 'ABAB' 对齐

两种规则的结合与最终跳转

Boyer-Moore 算法的最终跳转距离，是坏字符规则和好后缀规则计算出的跳转距离中的较大值。

最终跳转距离 = max(坏字符跳转距离, 好后缀跳转距离)

取最大值是为了确保我们跳过尽可能多的字符,同时保证不会错过可能的匹配。

C 语言实现步骤

实现 Boyer-Moore 算法，主要需要以下几个步骤：

预处理模式串：
- 坏字符表：创建一个数组或哈希表，记录模式串中每个字符最后出现的位置，这可以在 O(m) 时间内完成（m 是模式串长度）。
- 好后缀表：创建一个数组，记录对于每个可能的“好后缀”长度，模式串应该向右移动多少距离，这个表的构建稍微复杂一些，时间复杂度为 O(m)。
搜索过程：
- 初始化文本串的匹配起始位置。
- 循环进行匹配,直到模式串完全匹配或超出文本串范围。
- 从后向前比较字符。
- 如果发生不匹配,同时使用坏字符表和好后缀表计算跳转距离。
- 取两个距离的最大值,移动模式串的起始位置。
- 重复直到找到所有匹配或搜索结束。

C 语言代码实现

下面是一个完整的 C 语言实现，包含了坏字符和好后缀规则，为了简化，我们假设字符集是 ASCII。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 模式串长度
#define MAX_PATTERN_LEN 256
// 坏字符表: 记录每个字符在模式串中最后出现的位置
// -1 表示该字符不在模式串中
void preprocess_bad_char(const char *pattern, int pattern_len, int bad_char[256]) {
    for (int i = 0; i < 256; i++) {
        bad_char[i] = -1;
    }
    for (int i = 0; i < pattern_len; i++) {
        // 记录字符 pattern[i] 最后出现的位置
        bad_char[(unsigned char)pattern[i]] = i;
    }
}
// 好后缀表
// suffix[i] = k 表示模式串中 P[i+1...m-1] 是 P[k...m-1] 的后缀
// bpos[i] = k 表示 P[i+1...m-1] 的最长匹配前缀的起始位置是 k
void preprocess_good_suffix(const char *pattern, int pattern_len, int *suffix, int *bpos) {
    // 初始化
    int i = pattern_len, j = pattern_len + 1;
    suffix[i] = j;
    bpos[i] = j;
    while (i > 0) {
        // 模式串匹配
        while (j <= pattern_len && pattern[i - 1] != pattern[j - 1]) {
            if (suffix[j] == 0) {
                suffix[j] = i; // 设置好后缀表的值
            }
            j = bpos[j]; // 使用已经计算好的 bpos 进行跳跃
        }
        i--;
        j--;
        bpos[i] = j; // 记录最长匹配前缀的起始位置
        suffix[i] = j; // 记录好后缀表的值
    }
    // 特殊情况处理：模式串前缀是好后缀的后缀
    j = bpos[0];
    for (i = 0; i <= pattern_len; i++) {
        if (suffix[i] == 0) {
            suffix[i] = j;
        }
        if (i == j) {
            j = bpos[j];
        }
    }
}
// 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;
    }
    int bad_char[256];
    preprocess_bad_char(pattern, pattern_len, bad_char);
    int *suffix = (int *)malloc((pattern_len + 1) * sizeof(int));
    int *bpos = (int *)malloc((pattern_len + 1) * sizeof(int));
    preprocess_good_suffix(pattern, pattern_len, suffix, bpos);
    int s = 0; // 文本串中当前对齐的起始位置
    while (s <= (text_len - pattern_len)) {
        int j = pattern_len - 1; // 从模式串末尾开始比较
        // 从后向前匹配
        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }
        // j < 0，表示找到了一个完整匹配
        if (j < 0) {
            printf("Pattern found at index %d\n", s);
            // 使用好后缀规则继续向后搜索
            s += (s + pattern_len < text_len) ? suffix[0] : pattern_len;
        } else {
            // 坏字符规则：计算跳转距离
            // bc_offset 是模式串中坏字符最后一次出现的位置
            // 如果坏字符不存在，bc_offset 为 -1
            int bc_offset = bad_char[(unsigned char)text[s + j]];
            // 实际跳转距离是 (j - bc_offset)
            // 但不能为负数，所以取 max(1, j - bc_offset)
            int bc_shift = j - bc_offset;
            // 好后缀规则：计算跳转距离
            // j+1 个字符是好后缀，那么对应的跳转距离是 suffix[j+1]
            int gs_shift = suffix[j + 1];
            // 最终跳转距离是两个规则中较大的一个
            s += (bc_shift > gs_shift) ? bc_shift : gs_shift;
        }
    }
    free(suffix);
    free(bpos);
}
int main() {
    const char *text = "ABAAABCDABCDABDEABACDABABCABAB";
    const char *pattern1 = "ABABCABAB";
    const char *pattern2 = "CDAB";
    printf("Text: %s\n\n", text);
    printf("Searching for pattern: %s\n", pattern1);
    boyer_moore_search(text, pattern1);
    printf("\nSearching for pattern: %s\n", pattern2);
    boyer_moore_search(text, pattern2);
    return 0;
}

代码解释

preprocess_bad_char:
- 这个函数非常直接,它遍历模式串，将每个字符的最后出现位置记录在 bad_char 数组中，数组的索引是字符的 ASCII 码值。
preprocess_good_suffix:
- 这是实现中最复杂的部分,它构建了两个辅助数组 suffix 和 bpos。
- bpos (border position) 用于帮助快速查找模式串中与好后缀匹配的前缀。
- suffix 数组存储了最终的跳转信息。suffix[k] 的值表示当好后缀长度为 k 时，模式串应该向右移动的距离。
- 这个预处理过程的核心思想是利用已经计算好的信息来加速后续的计算,是一种动态规划的思想。
boyer_moore_search:
- 初始化：获取文本和模式的长度，进行预处理。
- 主循环：while (s <= text_len - pattern_len) 确保模式串不会超出文本串范围。
- 匹配：while (j >= 0 && pattern[j] == text[s + j]) 从后向前尝试匹配。
- 成功匹配 (j < 0)：打印匹配位置，根据好后缀表 suffix[0] 来移动 s，继续查找下一个可能的匹配。
- 匹配失败：
  - 坏字符跳转：bc_shift = j - bad_char[text[s + j]]。j 是当前不匹配的位置，bad_char[text[s + j]] 是坏字符在模式串中的位置，它们的差值就是坏字符规则建议的跳转距离。
  - 好后缀跳转：gs_shift = suffix[j + 1]，直接从预计算好的 suffix 表中获取跳转距离。
  - 取最大值：s += (bc_shift > gs_shift) ? bc_shift : gs_shift;，这是算法的关键，选择最优的跳转方式。

优点：平均时间复杂度为 O(n/m)，n 是文本串长度，m 是模式串长度，在最坏情况下（文本串是 AAAAA...，模式串是 BAAAA），时间复杂度为 O(n*m)，但这种情况在实际中很少见。
缺点：预处理（特别是好后缀表）相对复杂，需要额外的 O(m) 空间。
适用场景：当模式串较长，且字符集较大时，Boyer-Moore 算法通常表现非常出色，是许多文本编辑器和搜索引擎中使用的核心算法之一。

希望这个详细的解释和代码能帮助你理解如何在 C 语言中实现 Boyer-Moore 算法！

c语言boyermoore