关于 Rabin-Karp 算法

简介 #

在计算机科学中，拉宾-卡普算法（英语：Rabin–Karp algorithm），是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数在文本中搜寻单个模式串的字符串搜索算法。

该算法使用滚动哈希快速地跳过哈希不匹配的子串，只在哈希匹配时才对比整个模式串的每个字符。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。

Java 实现 #

只要不发生或极少发生哈希碰撞，Rabin–Karp 算法能发挥出 O(n) 的时间复杂度，而哈希碰撞发生的概率是很低的，还有它的空间复杂度是 O(1)，所以 Rabin–Karp 算法是我个人比较推荐的字符串搜索算法，其 Java 实现如下：

public final class RabinKarpAlgorithm {

    private RabinKarpAlgorithm() {
        // private
    }

    static final int PRIME = 16777619;

    /**
     * 不发生哈希碰撞时，时间复杂度为 O(n)；全都哈希碰撞时，时间复杂度为 O(nm)
     */
    public static int search(String str, String target) {
        int n = str.length(), m = target.length();
        if (n < m) return -1;
        int p = PRIME, maxPow = pow(p, m - 1);
        int t = rollingHash(target, m, p);
        int hash = rollingHash(str, m, p);
        for (int i = 0, end = n - m; i < end; i++) {
            if (hash == t && str.regionMatches(i, target, 0, m)) return i;
            hash = (hash - str.charAt(i) * maxPow) * p + str.charAt(i + m);
        }
        return -1;
    }

    /**
     * 快速幂，时间复杂度 O(log n)
     */
    public static int pow(int x, int n) {
        int a = 1;
        while (n > 0) {
            if ((n & 1) == 1) a *= x;
            x *= x;
            n >>= 1;
        }
        return a;
    }

    static int rollingHash(String str, int count, int p) {
        int hash = 0, pow = 1;
        for (int i = count - 1; i >= 0; i--) {
            hash += str.charAt(i) * pow;
            pow *= p;
        }
        return hash;
    }
}

其实在实际应用中，Rabin-Karp 算法只在一些特殊情况下比暴力搜索算法有优势， 更多时候性能并不如暴力搜索，因为 Rabin-Karp 算法每次循环涉及两次乘法， 每次乘法大约相当于数百次的 == 比较。

参考 #

• Rabin–Karp algorithm
• Rabin fingerprint