用C语言写一个基于Boyer-Moore算法的字符串子串查找匹配函数

Boyer-Moore算法是一种高效的字符串匹配算法，它通过跳过尽可能多的字符来加速搜索过程。该算法主要利用两个启发式规则：坏字符规则和好后缀规则。

下面是一个用C语言实现的基于Boyer-Moore算法的字符串子串查找匹配函数：

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

#define ALPHABET_SIZE 256 // 假设使用扩展ASCII码

// 计算坏字符表
void preprocessBadChar(char *pattern, int m, int badChar[ALPHABET_SIZE]) {
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        badChar[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        badChar[(unsigned char)pattern[i]] = i;
    }
}

// 计算好后缀表
void preprocessGoodSuffix(char *pattern, int m, int goodSuffix[m]) {
    int f = 0, g, i;
    goodSuffix[m - 1] = m;
    g = m - 1;
    for (i = m - 2; i >= 0; --i) {
        if (i > g && goodSuffix[i + m - 1 - f] < i - g) {
            goodSuffix[i] = goodSuffix[i + m - 1 - f];
        } else {
            if (i < g) {
                g = i;
            }
            f = i;
            while (g >= 0 && pattern[g] == pattern[g + m - 1 - f]) {
                --g;
            }
            goodSuffix[i] = f - g;
        }
    }
}

// Boyer-Moore字符串匹配算法
void boyerMooreSearch(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int badChar[ALPHABET_SIZE];
    int goodSuffix[m];

    preprocessBadChar(pattern, m, badChar);
    preprocessGoodSuffix(pattern, m, goodSuffix);

    int s = 0; // s是模式相对于文本的位移量
    while (s <= (n - m)) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[s + j]) {
            --j;
        }
        if (j < 0) {
            printf("Pattern occurs at shift = %d\n", s);
            s += (s + m < n) ? m - badChar[(unsigned char)text[s + m]] : 1;
        } else {
            s += (j - badChar[(unsigned char)text[s + j]] > goodSuffix[j] ? j - badChar[(unsigned char)text[s + j]] : goodSuffix[j]);
        }
    }
}

int main() {
    char text[] = "ABAAABCDABC";
    char pattern[] = "ABC";
    boyerMooreSearch(text, pattern);
    return 0;
}

这段代码首先定义了两个预处理函数`preprocessBadChar`和`preprocessGoodSuffix`，分别用于计算坏字符表和好后缀表。然后实现了`boyerMooreSearch`函数，该函数使用Boyer-Moore算法在给定的文本中查找模式字符串的所有出现位置。最后，在`main`函数中测试了这个搜索函数。