前置知识

我们记字符集为 $\Sigma$，字符串是由若干字符集中的元素构成的序列。

字符串哈希

即序列哈希，快速比较两个序列的相等情况。一般来讲我们采用 $b$ 进制方式的哈希，即 $f(s)=\sum_{i=1}^{l}s_i\times b^{l-i}$。

1

inline u64 q(u64 *f, int l, int r) { return f[r] - f[l - 1] * p[r - l + 1]; }