在介绍Rabin Karp算法前，先看看简单文本搜索算法。

简单文本搜索

遍历文本，如果模式的第一个字母匹配，则检查模式的所有字母是否都与文本匹配。
如果 m 是要搜索的字母数，n 是被搜索文本中的字母数，则该算法的时间复杂度为 O（m（n-m + 1））。

public static int simpleTextSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;

int i = 0;

while ((i + patternSize) <= textSize) {
    int j = 0;
    while (text[i + j] == pattern[j]) {
        j += 1;
        if (j >= patternSize)
            return i;
    }
    i += 1;
}
return -1;

}
当模式很长并且模式中有很多重复元素时，简单文本搜索算法效率非常低。、

Rabin Karp算法

Rabin Karp 算法的想法是使用哈希来查找文本中的模式。在算法开始时，我们需要计算模式的哈希值，该哈希值稍后在算法中使用。这个过程叫做指纹计算。
预处理步骤的重要之处在于其时间复杂度为 O（m），通过文本迭代将需要 O（n），从而给出整个算法的时间复杂度 O（m+n）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static int RabinKarpMethod(char[] pattern, char[] text) {
    int patternSize = pattern.length;
    int textSize = text.length;      

    long prime = getBiggerPrime(patternSize);

    long r = 1;
    for (int i = 0; i < patternSize - 1; i++) {
        r *= 2;
        r = r % prime;
    }

    long[] t = new long[textSize];
    t[0] = 0;

    long pfinger = 0;

    for (int j = 0; j < patternSize; j++) {
        t[0] = (2 * t[0] + text[j]) % prime;
        pfinger = (2 * pfinger + pattern[j]) % prime;
    }

    int i = 0;
    boolean passed = false;

    int diff = textSize - patternSize;
    for (i = 0; i <= diff; i++) {
        if (t[i] == pfinger) {
            passed = true;
            for (int k = 0; k < patternSize; k++) {
                if (text[i + k] != pattern[k]) {
                    passed = false;
                    break;
                }
            }

            if (passed) {
                return i;
            }
        }

        if (i < diff) {
            long value = 2 * (t[i] - r * text[i]) + text[i + patternSize];
            t[i + 1] = ((value % prime) + prime) % prime;
        }
    }
    return -1;

}