Karp-Rabin 字符串匹配算法詳解

Karp-Rabin 字符串匹配算法概述

Karp-Rabin 算法是一種基於哈希函數的字符串匹配算法，由 Richard Karp 和 Michael Rabin 於 1987 年提出。該算法利用滾動哈希技術，在預處理階段以 O(m) 時間計算模式串的哈希值，在搜索階段通過快速重新計算哈希值來比較文本子串與模式串，期望運行時間為 O(n+m)，雖然最壞情況下為 O(mn)。

核心特性

• 使用哈希函數進行字符串相似度比較
• 預處理階段時間復雜度 O(m)，佔用常數空間
• 搜索階段最壞時間復雜度 O(mn)
• 期望運行時間 O(n+m)

算法原理

傳統朴素匹配需逐字符比較，而 Karp-Rabin 算法通過哈希函數將字符串映射為數值，僅比較哈希值是否相等。若哈希值相等，再進行逐字符驗證以避免哈希碰撞導致的誤判。

理想哈希函數特性

1. 高效可計算
2. 對字符串高度識別（碰撞概率低）
3. 支持滾動計算：hash(y[j+1..j+m]) = rehash(y[j], y[j+m], hash(y[j..j+m-1]))

哈希函數定義

對於長度為 m 的單詞 w，定義哈希值為：

hash(w[0..m-1]) = (w[0]*2^(m-1) + w[1]*2^(m-2) + ... + w[m-1]*2^0) mod q

其中 q 為一較大的質數。滾動哈希公式為：

rehash(a, b, h) = ((h - a*2^(m-1))*2 + b) mod q

算法流程

預處理階段

計算模式串 x 的哈希值 hash(x)，時間復雜度 O(m)，空間 O(1)。

搜索階段

對文本 y 中每個長度為 m 的窗口 y[j..j+m-1] 計算哈希值，與 hash(x) 比較：

• 若不相等，直接滑動窗口
• 若相等，逐字符驗證 x == y[j..j+m-1]

利用滾動哈希在 O(1) 時間更新窗口哈希值。

實例演示

模式串：GCAGAGAG（長度 8），文本串：GCATCGCAGAGAGTATACAGTACG

預處理得到 hash(y) = 17597。搜索過程中計算各窗口哈希值：

最終在第 6 次嘗試找到匹配，共進行 8 次字符比較。

C 語言實現

#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

int KR(char *x, int m, char *y, int n) {
    int d, hx, hy, i, j;
    /* 預處理：計算 d = 2^(m-1) */
    for (d = i = 1; i < m; ++i) d = (d << 1);
    for (hy = hx = i = 0; i < m; ++i) {
        hx = ((hx << 1) + x[i]);
        hy = ((hy << 1) + y[i]);
    }
    /* 搜索階段 */
    j = 0;
    while (j <= n - m) {
        if (hx == hy && memcmp(x, y + j, m) == 0)
            return j;
        hy = REHASH(y[j], y[j + m], hy);
        ++j;
    }
    return -1;
}

參考文獻

• Aho, A.V., 1990, Algorithms for finding patterns in strings
• Cormen, T.H. 等, 1990, Introduction to Algorithms, Chapter 34
• Crochemore, M., Hancart, C., 1999, Pattern Matching in Strings
• Gonnet, G.H., Baeza-Yates, R.A., 1991, Handbook of Algorithms and Data Structures
• Karp R.M., Rabin M.O., 1987, Efficient randomized pattern-matching algorithms, IBM J. Res. Dev. 31(2):249-260
• Sedgewick, R., 1988, Algorithms, Chapter 19
• Stephen, G.A., 1994, String Searching Algorithms, World Scientific