学习笔记-Rabin-Karp哈希

在数学一本通上看过这两人名字，现在又出现了...

思想：

用一个整数表示一个字符串

\(w_{str}\)=(\(a_0\) \(p^{n-1}\)+\(a_1\) \(p^{n-2}\)+...+\(a_{n-1}\) \(p^0\)) (\(MOD\) \(q\))
注意：

字符转换成\(a_n\)时最好不要转为0，例如遇到"a","aa","aaa"的情况
优越之处：

我们可以在O(1)内取出任意子串的Hash值

怎么实现？
- 记录下所有前缀的Hash值
我们知道

\(w_{pre_{i-1}}\) \(=(\) \(a_0\) \(p^{i-1}\)+\(a_1\) \(p^{i-2}\)+...+\(a_{i-1}\) \(p^0\)) (\(MOD\) \(q\))

\(w_{pre_{j}}\) \(=(\) \(a_0\) \(p^{j}\)+\(a_1\) \(p^{j-1}\)+...+\(a_{j}\) \(p^0\)) (\(MOD\) \(q\))

所以
- \(w_{str_{i,j}}\)
\(=(\) \(a_i\) \(p^{j-i}\)+\(a_{i+1}\) \(p^{j-i-1}\)+...+\(a_{j}\) \(p^0\))

\(=\) \(w_{pre_{j}}\) \(-\) \(w_{pre_{i-1}}\) \(p^{j-i+1}\) (\(MOD\) \(q\))

然而....

在做TJOI2017 DNA时我发现取模太慢了,不如用unsigned long long自然溢出，这样一下就快了很多。

同时还有一个优化技巧,预处理出p值的幂,这样也能快不少。
应用：
- 字符串匹配
  - 思路：
    
    和KMP一样是\(O(N+M)\)的时间复杂度，只需要遍历文本串比较哈希值就可以了。
  - 题目：
  这个比较多应该都找得到
- 求最长公共前缀（Longest Common Prefix）：
  
  给定两个字符串a,b，有m个询问，每次分别给出两个起始位置x,y，求a串从x开始，b串从y开始的最长公共前缀(LCP)长度；
  - 思路
    
    二分+RK Hash
    
    如上文预处理出每个前缀的Hash值，我们就能O(1)内求出子串Hash值，然后不断二分长度L就好了
    
    根据fstqwq的说法，时间复杂度 \(O(m\log L)\)
    
    然而，自己摸索出了一个骚操作(好象又在哪里听过这种做法？),用倍增,因为二分的上下届可能比较大，不如倍增来的快.
  - 题目：
  --update--
  
  TJOI2017DNA
  https://www.luogu.org/problemnew/show/P3763
  
  我的题解：https://www.luogu.org/blog/Rye-Catcher/solution-p3763
  
  luogu上搜中文和算法都没有，搜英文有一道CF的题不过要用树链剖分，可惜我现在的知识点不够;
  
  另外我惊人地发现一道JSOI2008火星人的题目和SP3109 STRLCP - Longest Common Prefix几乎一模一样

巴特西

学习笔记-Rabin-Karp哈希

最新文章

热门文章