11-27 08:57 阅读 136

关注

数据结构和算法 ＜字符串＞（七、字符串匹配 （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=ciRM−1+ci+1RM−2+...+ci+M−1R0(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+1RM−1+ci+2RM−2+...+ci+M−1R1+ci+1+M−1R0

这两个公式有什么关系呢？我的直觉告诉我是很有关系的

中间画了红线的部分 c_i 这部分是一样的，只不过R的指数h_i+1 比 h_i 乘以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−ciRM−1=ci+1RM−2+...+ci+M−1R0 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−ciRm−1)R+ci+1+M−1R0=hi∗R−ciRm+ci+1+M−1R0

这样我们就可以通过一次遍历，就把子串的哈希值计算出来，真的好巧妙啊。

7.3  代码

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

// 计算模式串的哈希值 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  总结

伪原创工具 SEO网站优化  https://www.237it.com/ 

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

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

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

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

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

作者：善良的小油条
链接：https://juejin.cn/post/7035174743217012749