滚动哈希与Rabin–Karp算法
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