张天昀的个人博客

滚动哈希与Rabin–Karp算法

2020年03月20日

Rolling Hash

Hk=c1ak1+c2ak2++cka0H_k = c_1 a^{k-1} + c_2 a^{k-2} + \dots + c_k a^0

特性:

  • 向右移动:Hk+1=a×Hk+ck+1H_{k+1} = a \times H_k + c_{k+1}
  • 向左移动:Hk1=HkckaH_{k-1} = \dfrac{H_k - c_k}{a}

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

Rabin-Karp算法

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

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

最长回文前缀

正着读的时候:

HL=c1ak1+c2ak2++cka0H_L = c_1 a^{k-1} + c_2 a^{k-2} + \dots + c_k a^0

反着读的时候:

HR=c1a0+c2a1++ckak1H_R = c_1 a^0 + c_2 a^{1} + \dots + c_k a^{k-1}

由此得到递推关系:

  • HL=a×HL+ck+1H_L' = a \times H_L + c_{k+1}
  • HR=HR+ck+1akH_R' = H_R + c_{k+1} a^k

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

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

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