[Blog] [Docs] [Code] [Slides] [About]

滚动哈希与Rabin–Karp算法

2020-03-20 12:58 CST

2020-04-10 19:27 CST

Rolling Hash

$$H_k = c_1 a^{k-1} + c_2 a^{k-2} + \dots + c_k a^0$$

特性:

  • 向右移动:$H_{k+1} = a \times H_k + c_{k+1}$
  • 向左移动:$H_{k-1} = \dfrac{H_k - c_k}{a}$

如果需要固定长度的滑动窗口,只需要把被移出的字符对应的哈希值从总和中减去即可。

Rabin-Karp算法

  • 首先计算匹配模式的哈希值
  • 创建同等长度的滑动窗口,依次计算哈希值,如果哈希值匹配则成功

每次滑动窗口移动时,哈希值计算是$O(1)$的,因此总复杂度$O(n)$。非常简单直观。

最长回文前缀

正着读的时候:

$$H_L = c_1 a^{k-1} + c_2 a^{k-2} + \dots + c_k a^0$$

反着读的时候:

$$H_R = c_1 a^0 + c_2 a^{1} + \dots + c_k a^{k-1}$$

由此得到递推关系:

  • $H_L’ = a \times H_L + c_{k+1}$
  • $H_R’ = H_R + c_{k+1} a^k$

其中$a^k$可以在每次循环时保持更新,不需要每次计算;当$H_L = H_R$时,找到了新的最长回文前缀,更新答案。时间复杂度$O(n)$。

参考例题:CodeForces 1326D Prefix-Suffix Palindrome

更新:最长回文前缀可以使用KMP算法解决。假设$S = A+ B$,其中$A$是回文串,令$S’ = S + # + rev(S) = A + B + # + B + A$,则$S'$的前缀数组中的最后一位即为最长回文前缀的长度。

<EOF>

Loading Comments By Disqus