使用C语言写一个基于BM算法的字符串子串查找函数

在C语言中，Bloom过滤器(Bloom Filter)通常用于空间效率较高的概率性查询场景，而不是精确的子串查找。但如果你想要实现Knuth-Morris-Pratt(KMP)算法[^2]，它是一种高效的字符串搜索算法，可以在文本串中查找指定模式串，这里我们展示一个简单的KMP算法实现：

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

// 定义辅助函数 next[]，存储模式串的next值
void compute_next(char pattern[], int next[]) {
    int len = strlen(pattern);
    next[0] = 0;
    int j = -1;
    for (int i = 1; i < len; ++i) {
        while (j != -1 && pattern[i] != pattern[j + 1]) {
            j = next[j];
        }
        if (pattern[i] == pattern[j + 1]) {
            ++j;
        }
        next[i] = j;
    }
}

// KMP搜索函数
int kmp_search(char text[], char pattern[]) {
    int len_text = strlen(text);
    int len_pattern = strlen(pattern);
    compute_next(pattern, next);

    int i = 0, j = 0;
    while (i < len_text) {
        if (text[i] == pattern[j]) {
            ++i;
            ++j;
        } else if (j != 0) {
            j = next[j - 1]; // 如果当前字符不匹配，尝试从next表中找到最近的匹配位置
        } else {
            ++i; // 文本字符与模式串开头不匹配，直接移动到下一个文本字符
        }

        // 如果找到匹配，返回起始索引，否则继续搜索
        if (j == len_pattern) {
            return i - len_pattern; // 返回模式串在文本中的开始位置
        }
    }
    return -1; // 没有找到匹配
}

int main() {
    char text[] = "j12345678Pjabaaabcan";
    char pattern[] = "Pjab";
    printf("Pattern found at position: %d\n", kmp_search(text, pattern));
    return 0;
}