Rolling Hash

一句话理解

Rolling Hash 用前缀哈希 O(1) 取子串。

为什么要学

比较两个子串是否相等。

讲解

h(l,r)=pre[r]-pre[l-1]*P^{r-l+1}。注意模意义下减法和幂。

例子

和数字的前缀和同一思想，只是乘的是 P 的幂。

常见错误

• 幂次数算错。
• 减法没加 MOD。