C語言字符串中的Boyer-Moore算法

Boyer-Moore算法是一種高效的字符串匹配算法，它在文本中搜索模式串（pattern）并返回匹配的位置

以下是一個簡單的C語言實現(xiàn)Boyer-Moore算法的示例：

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

// 計算跳躍表
void build_skip_table(const char *pattern, int pattern_len, int skip_table[]) {
    for (int i = 0; i < 256; i++) {
        skip_table[i] = pattern_len;
    }

    for (int i = 0; i< pattern_len - 1; i++) {
        skip_table[(unsigned char)pattern[i]] = pattern_len - i - 1;
    }
}

// Boyer-Moore算法
int boyer_moore_search(const char *text, const char *pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    if (pattern_len == 0) {
        return 0;
    }

    int skip_table[256];
    build_skip_table(pattern, pattern_len, skip_table);

    int k = pattern_len - 1;
    while (k< text_len) {
        int j = pattern_len - 1;
        while (j >= 0 && text[k] == pattern[j]) {
            k--;
            j--;
        }

        if (j < 0) {
            return k + 1;
        }

        k += skip_table[(unsigned char)text[k]];
    }

    return -1;
}

int main() {
    const char *text = "This is a simple text to search the pattern in.";
    const char *pattern = "pattern";

    int position = boyer_moore_search(text, pattern);
    if (position != -1) {
        printf("Pattern found at position: %d\n", position);
    } else {
        printf("Pattern not found.\n");
    }

    return 0;
}

這個示例中，boyer_moore_search函數(shù)接受兩個參數(shù)：要搜索的文本和要查找的模式串。build_skip_table函數(shù)用于構(gòu)建跳躍表，它存儲了每個字符在模式串中最后出現(xiàn)的位置。然后，我們遍歷文本并使用跳躍表進行快速匹配。如果找到匹配的位置，函數(shù)返回該位置的索引；否則，返回-1。