Rolling Hash
Hk=c1ak−1+c2ak−2+⋯+cka0
特性:
- 向右移动:Hk+1=a×Hk+ck+1
- 向左移动:Hk−1=aHk−ck
如果需要固定长度的滑动窗口,只需要把被移出的字符对应的哈希值从总和中减去即可。
Rabin-Karp算法
- 首先计算匹配模式的哈希值
- 创建同等长度的滑动窗口,依次计算哈希值,如果哈希值匹配则成功
每次滑动窗口移动时,哈希值计算是O(1)的,因此总复杂度O(n)。非常简单直观。
最长回文前缀
正着读的时候:
HL=c1ak−1+c2ak−2+⋯+cka0
反着读的时候:
HR=c1a0+c2a1+⋯+ckak−1
由此得到递推关系:
- HL′=a×HL+ck+1
- HR′=HR+ck+1ak
其中ak可以在每次循环时保持更新,不需要每次计算;当HL=HR时,找到了新的最长回文前缀,更新答案。时间复杂度O(n)。
参考例题:CodeForces 1326D Prefix-Suffix Palindrome
更新:最长回文前缀可以使用KMP算法解决。假设S=A+B,其中A是回文串,令S′=S+#+rev(S)=A+B+#+B+A,则S′的前缀数组中的最后一位即为最长回文前缀的长度。