Rabin-Karp字符串哈希算法

Rabin-Karp 算法

Rabin-Karp是一种基于Hash的高效的字符串搜索算法

问题

给定长度为n的字符串s (文本串)，长度为m的字符串t (模式串)
求t是否在s中出现过(t是否为s的子串)

朴素: 0(nm)
Rabin-Karp算法: 0(n + m)

思路:

计算s的每个长度为m的子串的Hash值(-一个宽度为m的滑动窗口滑过s)
检查是否与t的Hash值相等

选用的Hash函数:
把字符串看作一个b进制数(一个多项式) ,计算它(在十进制下)对p取模的值

举例:
取b= 131, p= 2^64
字符串foobar的Hash值为(a=1, b=2, f=6, o=15, r=18)
(61315 + 151314 + 15* 1313+2 1312+ 1131 + 18) mod 264

选取的b和p的值决定了Hash函数的质量
根据经验，b=131, 13331等, p为大质数,冲突概率极小
Hash值相等时可以再比对一下两个字符串 ,避免Hash碰撞问题

如何快速计算一个子串的Hash值?
s = “foobar”
先计算6个前缀子串的Hash值, 0(n):
H[i] = Hash(s[0… i-1]) = (H[i-1]*b + s[i- 1]) mod p

计算子串oba的的Hash值:
相当于b进制下两个数做减法(H[5]-H[2]b3)
fooba
-fo000
oba
Hash(s[l…r]) = (H[r + 1]- H[l] b^r-l+1)mod p, 0(1)

实战

28.实现strStr()
https://leetcode.cn/problems/implement-strstr/

class Solution {
public:
    int strStr(string haystack, string needle) {
        int b = 131, p = 1e9 + 7;
        int n = haystack.size();
        int m = needle.size();
        vector<long long> H(n + 1, 0);
        for(int i = 1; i <= n; i++){
            H[i] = (H[i - 1] * b + (haystack[i - 1] - 'a' + 1)) % p;
        }
        long long Hneedle = 0;
        long long powBm = 1;
        for(char ch : needle) {
            Hneedle = (Hneedle * b + (ch - 'a' + 1)) % p;
            powBm = powBm * b % p;
        }
        for(int l = 1;l <= n - m + 1; l++){
            int r = l + m -1;
            if(((H[r] - H[l - 1] * powBm) % p + p) % p == Hneedle){
                return l - 1;
            }
        }

        return -1;
    }
};
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

class Solution {
public:
    int strStr(string haystack, string needle) {
        int b = 131;
        int n = haystack.size();
        int m = needle.size();
        vector<unsigned long long> H(n + 1, 0);
        for(int i = 1; i <= n; i++)
            H[i] = H[i - 1] * b + (haystack[i - 1] - 'a' + 1);
        unsigned long long Hneedle = 0;
        unsigned long long powBM = 1;
        for(char ch : needle) {
            Hneedle = Hneedle * b + (ch - 'a' + 1);
            powBM = powBM * b;
        }
        for (int l = 1; l <= n - m + 1; l++) {
            int r = l + m - 1;
            if(H[r] - H[l - 1] * powBM == Hneedle)
                return l - 1;
        }

        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习