题解：P10468 兔子与兔子

· · 题解

一眼串串题。考虑 hash。

我们知道，算法竞赛中的 hash 值都是将字符串转为 X 进制数。

于是我们令 H_i 表示前 i 个字符组成的字符串的 hash 值，P_i 表示 X^i。

根据定义，我们有：

H_i=H_{i-1} \times X+S_i P_i=P_{i-1} \times X

对于区间 [l,r] 的子串，运用前缀和的思想，我们易得它的 hash 值：

H_r-H_{l-1} \times P_{r-l+1}

（H_{l-1} \times P_{r-l+1} 是为了让 H_{l-1} 与 H_r 位数一样）

然后对于每一次询问，将 l_1,r_1 与 r_1,r_2 分别代入上式，检验 hash 值是否相等即可。

单哈希实现、双哈希实现。均使用 unsigned long long 自然溢出。