当前位置：首页 > C > 正文

RK算法详解（C语言实现Rabin-Karp字符串匹配算法从零入门）

主机测评网
C
2025-12-11
958

在计算机科学中，RK算法（Rabin-Karp算法）是一种高效的字符串搜索算法，特别适用于在大文本中查找多个模式串。本教程将手把手教你用C语言实现RK算法，即使你是编程小白，也能轻松理解并掌握！

RK算法详解（C语言实现Rabin-Karp字符串匹配算法从零入门） RK算法 C语言字符串匹配 Rabin-Karp算法实现字符串搜索算法第1张

什么是RK算法？

RK算法由Michael O. Rabin和Richard M. Karp于1987年提出，核心思想是：通过哈希（Hash）函数将字符串转换为数值，先比较哈希值，若相等再逐字符验证。这样可以避免大量不必要的字符比较，提高效率。

RK算法特别适合以下场景：

在一个长文本中查找多个短模式串（如敏感词过滤）
需要快速预筛选可能匹配位置的场景

RK算法的核心：滚动哈希（Rolling Hash）

RK算法的关键在于“滚动哈希”技术。假设我们要在文本 T 中查找模式串 P，长度为 m。我们可以：

先计算 P 的哈希值 hash_p
再计算 T 中前 m 个字符的哈希值 hash_t
如果 hash_p == hash_t，则逐字符比对确认是否真正匹配
接着滑动窗口，利用前一个哈希值快速计算下一个子串的哈希值（这就是“滚动”）

滚动哈希公式（以基数d=256为例）：

new_hash = (d * (old_hash - text[old_start] * h) + text[new_end]) % q其中：- d 是字符集大小（如ASCII为256）- q 是一个大素数（用于减少哈希冲突）- h = d^(m-1) % q

C语言实现RK算法

下面是一个完整的、可运行的C语言RK算法实现。我们使用模运算和滚动哈希来高效计算子串哈希值。

#include <stdio.h>#include <string.h>// 计算 (x^y) % p 的函数long long power_mod(long long x, long long y, long long p) {    long long res = 1;    x = x % p;    while (y > 0) {        if (y & 1)            res = (res * x) % p;        y = y >> 1;        x = (x * x) % p;    }    return res;}// RK算法主函数void rabin_karp_search(char pat[], char txt[], int q) {    int m = strlen(pat);    int n = strlen(txt);    int i, j;    long long p = 0; // 模式串的哈希值    long long t = 0; // 文本当前窗口的哈希值    long long h;    int d = 256; // 字符集大小（ASCII）    // 计算 h = d^(m-1) % q    h = power_mod(d, m - 1, q);    // 计算模式串和文本前m个字符的哈希值    for (i = 0; i < m; i++) {        p = (d * p + pat[i]) % q;        t = (d * t + txt[i]) % q;    }    // 滑动窗口，逐个检查    for (i = 0; i <= n - m; i++) {        // 如果哈希值匹配，则逐字符验证        if (p == t) {            for (j = 0; j < m; j++) {                if (txt[i + j] != pat[j])                    break;            }            if (j == m)                printf("模式串在位置 %d 找到\n", i);        }        // 计算下一个窗口的哈希值（滚动哈希）        if (i < n - m) {            t = (d * (t - txt[i] * h) + txt[i + m]) % q;            // 处理负数情况            if (t < 0)                t = (t + q);        }    }}int main() {    char txt[] = "ABABCABABA";    char pat[] = "ABABA";    int q = 101; // 一个大素数    rabin_karp_search(pat, txt, q);    return 0;}