Rabin Karp Algorithm

Rabin Karp Algorithm

1. Introduction

将一个String转成相应的哈希值，假设string s的长度是m, 通过Rabin Karp算法，得到s[0...m - 1]的值为 s[0] * Base ^ (m - 1) + s[1] * Base ^ (m -2) + .... + s[m - 2] * Base ^ 1 + s[m - 1] * Base ^ 0

这里Base的值很关键，所以用Rabin Karp解题最大难点就是如何选择Base

2. Implementation

   // 以Strstr()为例
   public int strStr(String haystack, String needle) {
        // Rabin Karp Algorithm
        if (haystack.length() < needle.length()) {
            return -1;
        }

        String t = haystack;
        String s = needle;

        int BASE = 256;
        // Avoid overflow
        long sHash = 0, tHash = 0;
        long powerS = 1;

        for (int i = 0; i < s.length(); i++) {
            tHash = tHash * BASE + t.charAt(i);
            sHash = sHash * BASE + s.charAt(i);
            powerS *= BASE;
        }

        // powerS == BASE ^ (s.length() - 1)
        powerS /= BASE;

        for (int i = s.length(); i < t.length(); i++) {
            if (tHash == sHash && t.substring(i - s.length(), i).equals(s)) {
                return i - s.length();
            }

            tHash -= t.charAt(i - s.length()) * powerS;
            tHash = tHash * BASE + t.charAt(i);
        }

        if (tHash == sHash && t.substring(t.length() - s.length()).equals(s)) {
            return t.length() - s.length();
        }
        return -1;
    }

3. Time & Space Complexity

Time: O(n)

Space: O(1)