C语言字符串中的Rabin-Karp算法

Rabin-Karp算法是一种字符串匹配算法，用于在文本中查找模式字符串

以下是使用Rabin-Karp算法在C语言中实现字符串匹配的示例：

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

#define PRIME 101
#define D 256

// 计算字符串的哈希值
unsigned long hash(const char *str, int len) {
    unsigned long h = 0;
    for (int i = 0; i < len; ++i) {
        h = (D * h + str[i]) % PRIME;
    }
    return h;
}

// Rabin-Karp算法实现
void rabin_karp(const char *text, const char *pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    // 计算模式字符串的哈希值
    unsigned long pattern_hash = hash(pattern, pattern_len);

    // 遍历文本字符串
    for (int i = 0; i <= text_len - pattern_len; ++i) {
        // 计算子字符串的哈希值
        unsigned long sub_hash = hash(text + i, pattern_len);

        // 如果哈希值相等，则比较子字符串和模式字符串是否相等
        if (sub_hash == pattern_hash && strncmp(text + i, pattern, pattern_len) == 0) {
            printf("Pattern found at position: %d\n", i);
        }
    }
}

int main() {
    const char *text = "This is a test string for Rabin-Karp algorithm.";
    const char *pattern = "Rabin";

    rabin_karp(text, pattern);

    return 0;
}

这个示例中，我们首先定义了两个辅助函数hash()和rabin_karp()。hash()函数用于计算字符串的哈希值，而rabin_karp()函数实现了Rabin-Karp算法。在main()函数中，我们调用rabin_karp()函数来查找模式字符串在文本中的位置。