Rabin-Karp字符串查找算法

发表于 | 分类于

不同于传统的字符比较，本算法的核心在于散列。
先计算出子串 pat 的一个散列值，然后从文本 txt 中，从 i = 0 开始，计算从当前 i 开始的子串长度的字符串的散列，比如 pat = ‘250’，txt = ‘230240250’，计算的是 ‘230’、’302’、’024’的散列，依次类推，与’250’的散列值进行比较，如果散列值相同，再比较两个字符串是否匹配，当然会有散列冲突，但是可以把冲突几率降低，忽略不计，该算法是线性时间，前提是使用了Rabin-Karp发明的求散列值的算法。
基本思想

除留余数法

1
2
3
4
5
6
7
8
9
10
11
// 取余操作有一个基本性质，每次算数操作之后取余，等价于所有算数操作都结束后再取余
long jp_hash(char *key, int M) { // M是key的长度
    long result = 0;
    long Q = 997; // 除数，此处选一个大素数
    long R = 10; // 进制，此处选10
    for (int i = 0; i < M; ++i) {
        result = (result * R + key[i]) % Q;
    }
    
    return result;
}

以上，子串 pat 的散列值求完了。

然后
匹配过程中 txt 子串的散列值计算，即在 i 的基础上计算 i+1 的散列值。如图：
这里写图片描述

核心算法是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int jp_search(char *txt, char *pat) {
    long M = strlen(pat);
    long N = strlen(txt);
    
    long Q = 997; // 除数，此处选一个大素数
    long R = 10; // 进制，此处选10
    long RM = 30; // R^(M-1) % Q, 假设 M = 5，此处为10000 % 997 = 30
    long txt_hash = jp_hash(txt, (int)M);
    long pat_hash = jp_hash(pat, M);
    for (int i = M; i < N; ++i) {
        // 减去第一个数字，加上最后一个数字
        txt_hash = (txt_hash - RM * txt[i-M] % Q + Q) % Q;
        txt_hash = (txt_hash * R + txt[i]) % Q;
        
        if (txt_hash == pat_hash) {
            // 进行匹配，成功则返回，失败则continue
        }
    }
    return N; // 查找失败
}

比较难理解的应该是计算 txt_hash 的两句，这里还是应用了取余操作的基本原则，第二句里的txt_hash本来应该是数的值，但等价于该值取余之后的余数，所以第一句计算的是新子串的余数，即上一个txt_hash减去第一个字符的余数，然后第二句是加上新字符再次求余数即txt_hash，+Q是防止 txt_hash - RM * txt[i-M] % Q 这里出现负数。

参考：《算法》第四版

显示 Gitment 评论