字符串模式匹配bm算法C语言代码

字符串模式匹配的BM（Boyer-Moore 算法）是一种高效的文本搜索算法，它利用了坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule）。下面是一个简单的 C 语言实现，假设我们有一个文本 `text` 和一个模式 `pattern`：

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

// 定义函数来查找 pattern 在 text 中的位置
int BM_search(char* text, char* pattern) {
    int m = strlen(pattern); // 模式长度
    int n = strlen(text);   // 文本长度

    if (n < m) return -1; // 如果文本比模式短，则不可能找到

    // 好后缀表，记录每个位置之后最长公共前后缀的长度
    int suffix_table[m];

    // 初始化好后缀表
    for (int i = 0; i < m; ++i) {
        suffix_table[i] = m - i - 1;
    }
    for (int k = m - 2; k >= 0; --k) {
        if (pattern[k] == pattern[m - 1]) {
            suffix_table[k] = suffix_table[m - 1];
        } else {
            suffix_table[k] = k > 0 ? suffix_table[k - 1] : 0;
        }
    }

    int i = m - 1; // 当前字符位置
    while (i <= n - m) { // 遍历文本
        if (text[i] == pattern[i]) { // 同步字符
            if (i + m - 1 == n) { // 找到了
                return i;
            }
            i--; // 继续向后移动模式
        } else { // 使用好后缀规则跳过
            int skip = suffix_table[i]; // 跳过的字符数
            if (skip > 0 && i + skip < n && text[i + skip] == pattern[skip]) { // 如果可以同时跳跃模式和字符
                i += skip;
            } else { // 如果不行，直接从下一个字符开始寻找
                i++;
            }
        }
    }

    return -1; // 没有找到匹配
}

int main() {
    char text[] = "Hello, world!";
    char pattern[] = "world";
    int result = BM_search(text, pattern);
    if (result != -1)
        printf("Pattern found at index %d\n", result);
    else
        printf("Pattern not found.\n");
    return 0;
}