C語(yǔ)言字符串中的Rabin-Karp算法

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

以下是使用Rabin-Karp算法在C語(yǔ)言中實(shí)現(xiàn)字符串匹配的示例：

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

#define PRIME 101
#define D 256

// 計(jì)算字符串的哈希值
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算法實(shí)現(xiàn)
void rabin_karp(const char *text, const char *pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

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

    // 遍歷文本字符串
    for (int i = 0; i <= text_len - pattern_len; ++i) {
        // 計(jì)算子字符串的哈希值
        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;
}

這個(gè)示例中，我們首先定義了兩個(gè)輔助函數(shù)hash()和rabin_karp()。hash()函數(shù)用于計(jì)算字符串的哈希值，而rabin_karp()函數(shù)實(shí)現(xiàn)了Rabin-Karp算法。在main()函數(shù)中，我們調(diào)用rabin_karp()函數(shù)來(lái)查找模式字符串在文本中的位置。