C语言 Boyer-Moore算法

Boyer-Moore算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的位置。它的优势在于，在某些情况下，它比传统的字符串匹配算法（如KMP算法）更快。

算法的核心思想是尽可能地跳过主串中不可能存在匹配的位置。具体来说，算法分为两个阶段：预处理阶段和匹配阶段。在预处理阶段，算法需要构造两个数组：坏字符规则和好后缀规则。坏字符规则用于处理主串中与模式串不匹配的字符，好后缀规则用于处理模式串中的后缀字符串。

预处理阶段：
1. 对于模式串中的每个字符，记录它在模式串中最后一次出现的位置。
2. 对于模式串中的每个后缀，找到它在模式串中的另一个位置（不包括最后一个字符），使得该位置到模式串结尾的子串是模式串的后缀，并且该子串不是模式串的整个后缀。
3. 如果模式串中不存在好后缀，那么找到模式串中的最长前缀，使得该前缀等于模式串的后缀。

匹配阶段：
1. 从主串中的第一个字符开始，向右扫描。
2. 对于每个字符，从模式串的最后一个字符开始向左扫描，找到第一个不匹配的字符。
3. 根据坏字符规则和好后缀规则，计算下一次需要跳过的位置。
4. 如果模式串的最后一个字符已经匹配，那么找到了一个匹配。

下面是C语言实现的代码示例：

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

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))

void generate_bad_char_rule(char pattern[], int pattern_len, int bad_char_rule[]) {
    int i;
    for (i = 0; i < 256; i++) {
        bad_char_rule[i] = pattern_len;
    }
    for (i = 0; i < pattern_len; i++) {
        bad_char_rule[(int) pattern[i]] = pattern_len - i - 1;
    }
}

void generate_good_suffix_rule(char pattern[], int pattern_len, int good_suffix_rule[]) {
    int i, j;
    int prefix_len = pattern_len;
    good_suffix_rule[pattern_len - 1] = pattern_len;
    for (i = pattern_len - 2; i >= 0; i--) {
        if (prefix_len > i + 1 && pattern[i + 1] != pattern[prefix_len - 1]) {
            prefix_len = pattern_len - good_suffix_rule[pattern_len - prefix_len + i + 1];
        }
        good_suffix_rule[i] = prefix_len + i;
        for (j = 0; j < i; j++) {
            if (pattern[j] == pattern[pattern_len - i + j - 1]) {
                good_suffix_rule[i] = pattern_len - j - 1;
            }
        }
    }
}

int boyer_moore(char text[], int text_len, char pattern[], int pattern_len) {
    int i, j;
    int bad_char_rule[256];
    int good_suffix_rule[256];
    generate_bad_char_rule(pattern, pattern_len, bad_char_rule);
    generate_good_suffix_rule(pattern, pattern_len, good_suffix_rule);
    for (i = pattern_len - 1, j = i; i < text_len;) {
        if (pattern[j] == text[i]) {
            if (j == 0) {
                return i;
            }
            i--;
            j--;
        } else {
            i += bad_char_rule[(int) text[i]];
            j = pattern_len - 1;
        }
        if (i >= text_len) {
            break;
        }
        if (j == -1) {
            j = pattern_len - 1;
        }
        if (good_suffix_rule[j] < pattern_len - j + i) {
            i += pattern_len - j - 1;
            j = pattern_len - 1;
        }
    }
    return -1;
}

int main(int argc, char *argv[]) {
    char *text = "ABAAABCD";
    char *pattern = "ABC";
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);
    int index = boyer_moore(text, text_len, pattern, pattern_len);
    if (index >= 0) {
        printf("Pattern found at index %d\n", index);
    } else {
        printf("Pattern not found\n");
    }
    return 0;
}

在上面的代码中，`generate_bad_char_rule`函数用于生成坏字符规则，`generate_good_suffix_rule`函数用于生成好后缀规则，`boyer_moore`函数用于实现匹配。在主函数中，我们将一个文本串和一个模式串传递给`boyer_moore`函数，并打印出匹配结果。