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'$的前缀数组中的最后一位即为最长回文前缀的长度。