数据结构和算法 ＜字符串＞（七、字符串匹配 （RK算法））

发表于

RK算法的全称叫Rabin-Karp算法，是由它的两位发明者Rabin和karp的名字命名的。算法理解不算难，就是BF的升级版。

7.1 RK算法思路

在上一节介绍的BF算法的时候，我们是每次都检查主串和模式串是否匹配，需要依次对比每个字符，所以BF算法的时间复杂度很高，是O(n*m)。我们对暴力解法稍加改造，引入哈希算法，时间复杂度就会降低。

RK算法的思路是这样的，我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，（因为在暴力解法当中，也是跟n-m+1个子串进行比较），然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串的一样，（为了防止哈希碰撞，这时候我们再单独对比一下字符串）。因为这两个值都是数字，所以比较是否相等会非常快速，所以模式串和子串比较的效率就提高了。

在这里插入图片描述

但是如果需要遍历子串中的每个字符去计算哈希值，算法整体效率并没有提高，有什么办法提交效率？

7.2 哈希算法

这样的话，我们就需要重新设计一个哈希算法了。我们假设要匹配的字符串字符集中包含K个字符，我们可以用K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。

我们就按照上面的图来计算一下哈希值：（上面只有26个小写字母，我们可以看成26进制）

在这里插入图片描述

看了图应该懂了吧。就是按平常计算十进制的时候计算的。

虽然是这个样子，但好像我们写代码的时候也是需要遍历的，如果是这样，那我们为什么提议这个哈希算法呢？

根据我们看图，h1 和 h2就有很明显的关系。

hi=ciRM−1+ci+1RM−2+…+ci+M−1R0(R是进制，M是子串长度)h_i = c_iR^{M-1}+c_{i+1}R^{M-2}+…+c_{i+M-1}R^{0} (R是进制，M是子串长度)hi​=ci​RM−1+ci+1​RM−2+…+ci+M−1​R0(R是进制，M是子串长度)
hi+1=ci+1RM−1+ci+2RM−2+…+ci+M−1R1+ci+1+M−1R0h_{i+1} = c_{i+1}R^{M-1}+c_{i+2}R^{M-2}+…+c_{i+M-1}R^{1}+c_{i+1+M-1}R^{0}hi+1​=ci+1​RM−1+ci+2​RM−2+…+ci+M−1​R1+ci+1+M−1​R0
这两个公式有什么关系呢？我的直觉告诉我是很有关系的

在这里插入图片描述

中间画了红线的部分 ci 这部分是一样的，只不过R的指数hi+1 比 hi 乘以R。

所以我们把公式转换一下：

hi−ciRM−1=ci+1RM−2+…+ci+M−1R0h_i - c_iR^{M-1} = c_{i+1}R^{M-2}+…+c_{i+M-1}R^{0}hi​−ci​RM−1=ci+1​RM−2+…+ci+M−1​R0
hi+1=(hi−ciRm−1)R+ci+1+M−1R0=hi∗R−ciRm+ci+1+M−1R0h_{i+1} = (h_i - c_iR^{m-1})R + c_{i+1+M-1}R^{0} = h_i *R - c_iR^m + c_{i+1+M-1}R^{0}hi+1​=(hi​−ci​Rm−1)R+ci+1+M−1​R0=hi​∗R−ci​Rm+ci+1+M−1​R0
这样我们就可以通过一次遍历，就把子串的哈希值计算出来，真的好巧妙啊。

7.3 代码

上一个代码先，虽然思想已经懂了，但是还是多写代码，熟悉一下，有刷过leetcode的应该都记得，这种用哈希来保存题很多，所以就借这这次来实现一个代码。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
c复制代码// 计算模式串的哈希值
long RK::hash_base(std::string pat, int M, int R)
{
    // 计算
    long RM = 0;
    for(int i = 0; i < M; i++)
    {
        
        RM += (pat.at(i) - 'a') * pow(R, M-1-i);
        // printf("pat.at(%d) - 'a' = %d %lf %ld\n", i, pat.at(i) - 'a', pow(R, M-1-i), RM);
    }

    // printf("Rm %ld\n", RM);
    return RM;
}


// 准备主串的哈希值
int RK::string_hash(std::string txt, int M, int R, std::unordered_map<long, int> &mymap)
{
    int N = txt.length();
    long h = hash_base(txt, M, R);      // 计算前面M个哈希值
    mymap[h] = 0;
    //printf("h = %ld\n", h);
    for(int i = 1; i< N-M+1; i++)
    {
        //printf("ddd %ld %d %d\n", h * 26, (txt.at(i-1) - 'a') * pow(R, M) , (txt.at(i-1+1+M-1) - 'a'));
        h = h * R - (txt.at(i-1) - 'a') * pow(R, M) + (txt.at(i-1+1+M-1) - 'a');
        
        mymap[h] = i;
       //mymap.insert(std::make_pair(h, i));
       //printf("h = %ld\n", h);
    }

    return 0;
}


int RK::search(std::string pat, std::string txt, int R)
{
    int N = txt.length();
    int M = pat.length();
    std::unordered_map<long, int> mymap;
    printf("search %d %d\n", N, M);

    long pat_hash = hash_base(pat, M, 26);
    printf("pat_hash %d\n", pat_hash);
    string_hash(txt,  M, R, mymap);
    
    // for(std::unordered_map<long, int>::iterator it = mymap.begin(); it != mymap.end(); it++) {
    //         std::cout << "one " << it->first << "  two " << it->second << std::endl;
    // }


    auto itr = mymap.find(pat_hash);
    if(itr != mymap.end())
    {
        // 这里可以判断一下，然后处理哈希碰撞问题
        printf("itr %d %d\n", itr->first, itr->second);
        return itr->second;
    }

    printf("return 0");

    return 0;
}

写了代码之后才发现确实不熟练，还是需要多加练习。

代码路径：RK.cpp

7.4 总结

代码写完了，接下来看看时间复杂度是多少了。（其实可以不用存到哈希中，只要计算模式字符串的哈希，然后主串主要计算前面一个值，然后等到模式串匹配的时候再计算，这个是《算法4》中采用的）

整个RK算法分两部分：第一部分就是计算主串的哈希值，明显可以看出是O(n)，然后对比的时候，我是使用存储到哈希中，用find函数，所以也是O(1)，整体的复杂度为O(n)。

还有一个问题：如果模式串很长，响应的主串也很长，通过上面的哈希计算函数得到的哈希值很大，如果超出了计算机的整形数据范围，那该如何解决？

这是我们上面设计的哈希算法的问题，因为是用进制的方式计算的，当然很大了，所以我们需要考虑允许一些哈希碰撞，《算法4》中提议的是随机一个素数Q，把计算出来的哈希值模Q,这样也是一个方法，感觉还不错。如果哈希碰撞了，怎么办，上面我也提过了，如果真的哈希值一样，我们可以对比一个模式串和子串的值就可以了。这也消耗不了太多时间。

所以需要控制哈希算法的冲突概率，如果存在大量冲突，就会导致RK算法时间复杂度退化。严重会退化到O(n*m)。一般情况下，冲突不会很多，RK算法效率很是比BF算法高的。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%