数据结构和算法

字符串匹配算法（二）——Rabin-Karp算法

Rabin-Karp设计了一个巧妙的hash算法。用到的数学公式为：t(s+1) = (d(t(s)-T[s+1]h)+T[s+m+1]) mod q
t(s+1)为目标字符串的子字符串T[s+1,s+m+1]的哈希值，因为用到了上一次的结果t(s)，所以可以节省计算时间。

首先计算pattern字符串的hash值，然后在从目标字符串的开头，计算相同长度字符串的hash值。若hash值相同，则表示匹配，若不同，则向右移动一位，计算新的hash值。整个过程，与暴力的字符串匹配算法很相似，但由于计算hash值时，可以利用上一次的hash值，从而使新的hash值只需要加上新字母的计算，并减去上一次的第一个字母的计算，即可。

Rabin-Karp算法的预处理时间为O(m)，最坏情况下该算法的匹配时间为O((n-m+1)m)。但是平均运行时间还是比较好的。

用C语言实现如下：

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
#include <stdio.h>
#include <math.h>

int mod = 0x7fffffff;
const int d = 128;

int rabin_karp(char *T, char *P, int n, int m)
{
    if (n < m) return -2;
    int h = pow(d, m-1);
    int p = 0;
    int t = 0;
    int i, j;
    for (i=0; i<m; i++) {
        p = (d*p + P[i]) % mod;
        t = (d*t + T[i]) % mod;
    }
    for (j=0; j<=n-m; j++) {
        if (p == t) {
            return j;
        }
        if (j < n-m) {
            t = (d*(t - h*T[j]) + T[j+m]) % mod;
        }
    }
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    int len1 = sizeof(t) - 1;
    int len2 = sizeof(p) - 1;
    int index = rabin_karp(t, p, len1, len2);
    printf("index: %d\n", index);
    return 0;
    return 0;
}

现在结合上面的公式和代码再进行讲解一下。
d表示字母表的字母个数，上面的代码只接受ascii值为0~127的字符。如果采用小写英文字母来做字母表的话，那么d就是26。
h等于d^(m-1) % q。其实模q运算应该是可有可无的，加入q应该是为了避免数据溢出。但是加入模q后，由ts == p mod q不能说明ts == p，不过ts != p mod q则可以肯定ts != p。所以q最好选择比较大的质数，并且选取的q要满足使dq的值在一个计算机字长内。如果使用的是动态的编程语言的话就不用担心数据溢出，因此就不用进行模q运算。