Rabin-Karp指纹字符串查找算法

Rabin-Karp 指纹字符串查找算法

算法首先计算模式字符串（Pattern）的散列值（Hash Value）。如果在文本字符串（Text）中找到一个子字符串，其散列值与模式字符串的散列值相同，则继续验证两者是否完全匹配。

这个过程等价于将模式字符串保存在一个散列表中，然后在文本的所有子字符串中进行查找。但由于只需要匹配一个模式，因此不需要为散列表预留额外空间。

基本思想

长度为 $M$ 的字符串可以对应着一个 $R$ 进制的 $M$ 位数。为了用一张大小为 $Q$ 的散列表来保存这种类型的键，需要一个散列函数，能够将 $R$ 进制的 $M$ 位数转化为一个 $0$ 到 $Q-1$ 之间的整数值。这里通常使用除留取余法。

举个例子，需要在文本 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 中查找模式 2 6 5 3 5。这里设 $R=10$，取质数 $Q=997$，则模式字符串的散列值为：

$$26535 \pmod{997} = 613$$

然后计算文本中所有长度为 5 的子字符串的散列值并寻找匹配：

3 1 4 1 5 % 997 = 508
1 4 1 5 9 % 997 = 201
...
2 6 5 3 5 % 997 = 613 (匹配)

散列函数计算

对于较短的数值，直接使用 int 或 long 即可完成计算。但当模式长度较大时，数值可能会溢出，此时我们使用 Horner 方法（秦九韶算法）边计算边取余。

以下展示模式 2 6 5 3 5 的散列值计算过程：

$2 \pmod{997} = 2$
$26 \pmod{997} = (2 \times 10 + 6) \pmod{997} = 26$
$265 \pmod{997} = (26 \times 10 + 5) \pmod{997} = 265$
$2653 \pmod{997} = (265 \times 10 + 3) \pmod{997} = 659$
$26535 \pmod{997} = (659 \times 10 + 5) \pmod{997} = 613$

这里的关键在于不需要保存中间的大数值，只需保存它们除以 $Q$ 之后的余数。取余操作的一个基本性质是：如果每次算术操作之后都将结果除以 $Q$ 并取余，这等价于在完成所有算术操作之后再将最后的结果除以 $Q$ 并取余。

滚动散列更新

在文本中滑动窗口计算散列值时，不需要重新计算每个子字符串的散列值，而是利用前一个子字符串的散列值进行更新。

假设当前窗口散列值为 txtHash，窗口长度为 $M$，最高位字符对应的权重为 $RM = R^{M-1} \pmod Q$。当窗口向右移动一位时：

减去最高位字符的贡献。
整体乘以 $R$（左移）。
加上新进入窗口的最低位字符。

以下展示文本前几个窗口的滚动计算过程（$R=10, Q=997, RM=30$）：

初始窗口 3 1 4 1 5：
3 1 4 1 5 % 997 = 508
滑动至 1 4 1 5 9：
移除首位 3，加入末位 9。
$$((508 - 3 \times 30) \times 10 + 9) \pmod{997} = 201$$
(注：代码中为避免负数取余问题，常写作 (txtHash + Q - RM * oldChar % Q) % Q)
滑动至 4 1 5 9 2：
$$((201 - 1 \times 30) \times 10 + 2) \pmod{997} = 715$$
...
滑动至匹配窗口 2 6 5 3 5：
计算得到散列值 613，与模式散列值一致。

构造函数为模式字符串计算了散列值 patHash 并在变量中保存了 $R^{M-1} \pmod Q$ 的值。search() 方法计算了文本前 $M$ 个字符的散列值并与模式字符串的散列值比较；如果没有匹配，文本指针继续下移一位，利用滚动哈希计算新的散列值再次比较，直到成功匹配或遍历结束。

代码实现

以下是基于 Java 的实现示例。注意代码中使用了 edu.princeton.cs.algs4 库中的工具类。

import java.math.BigInteger;
import java.util.Random;

import edu.princeton.cs.algs4.StdOut;

public class RabinKarp {
    private String pat;      // 模式字符串
    private long patHash;    // 模式字符串散列值
    private int M;           // 模式字符串的长度
    private long Q;          // 很大的素数
    private int R;           // 字母表的大小
    private long RM;         // R^(M-1) % Q

    public RabinKarp(char[] pat, int R) {
        this.pat = String.valueOf(pat);
        this.R = R;
    }
    
    public RabinKarp(String pat) {
        this.pat = pat;
        R = 256;
        M = pat.length();
        Q = longRandomPrime();
        
        RM = 1;
        for (int i = 1; i <= M - 1; i++) {
            RM = (R * RM) % Q;
        }
        patHash = hash(pat, M);
    }
    
    private long hash(String str, int M) {
        long h = 0;
        for (int i = 0; i < M; i++) {
            h = (R * h + str.charAt(i)) % Q;
        }
        return h;
    }
    
    // 验证匹配，防止散列冲突
    public boolean check(String txt, int i) {
        for (int j = 0; j < M; j++) {
            if (pat.charAt(j) != txt.charAt(i + j))
                return false;
        }
        return true;
    }
    
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }
    
    private int search(String txt) {
        int N = txt.length();
        if (N < M) return N;
        long txtHash = hash(txt, M);
        
        if ((txtHash == patHash) && check(txt, 0)) return 0;
        for (int i = M; i < N; i++) {
            // 删除前导字符，添加新字符，计算滚动散列
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            int offset = i - M + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }
        return N;
    }
    
    public static void main(String[] args) {
        String pat = args[0];
        String txt = args[1];

        RabinKarp searcher = new RabinKarp(pat);
        int offset = searcher.search(txt);
        
        // 打印结果
        StdOut.println("text:    " + txt);

        // 显示模式匹配位置
        StdOut.print("pattern: ");
        for (int i = 0; i < offset; i++)
            StdOut.print(" ");
        StdOut.println(pat);
    }
}

说明

依赖库：上述代码引用了 edu.princeton.cs.algs4.StdOut，这是 Princeton University 算法课程（《Algorithms 4th Edition》）的标准库。若在独立环境中运行，需替换为标准输出或引入相应依赖。
散列冲突：代码中的 check 方法用于二次验证，以防止不同的字符串拥有相同的散列值（冲突）。
大数运算：文中涉及的求模运算方法参考了初等数论中的同余定理。对于极大的字符串或特定的安全需求，可调整素数 $Q$ 的大小。

本文地址：https://1diff.fun/archives/rabin-karp-zhi-wen-zi-fu-chuan-cha-zhao-suan-fa.html

如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。

Rabin-Karp指纹字符串查找算法