Biu
字符串前缀哈希法。预处理出所有字符串前缀的哈希，数组存储，下标从 1 开始存储。
将字符串看成一个 p 进制的数，例如前缀"ABCD"的哈希值：把这个字符串看出 p 进制的数，那么这个值就是： h a s h [ 4 ] = ( 1 ∗ p 3 + 2 ∗ p 2 + 3 ∗ p 1 + 4 ∗ p 0 ) % m o d ； hash[4] = (1 * p^3 + 2 * p^2 + 3 * p^1 + 4 * p^0 ) \% mod； hash[4]=(1∗p3+2∗p2+3∗p1+4∗p0)%mod；
关于 mod 的经验值，131 或者 13331，冲突几率可以忽略不计。
特殊注意：
不能将某一个字符映射成数字 0，如果一旦 A 映射成了数字 0，那么 AA 也是数字 0，所以映射成从 1 开始这里的哈希字符串方法是假定不存在冲突的，取上述的模数经验值即可这样的哈希方式，配合前缀哈希方式可以求出任意一个子串的哈希值，类似于预处理了前缀和，现求子区间和，公式为： h [ R ] − h [ L ] ∗ p R − ( L − 1 ) h[R] - h[L]*p^{R-(L-1)} h[R]−h[L]∗pR−(L−1)
我们可以采用 unsigned long long 的溢出来代替取模 2^64 。
模板：
#include <iostream> using namespace std; typedef unsigned long long ULL; const int N = 1e5+5, mod = 13331; int n, m; char str[N]; ULL h[N], p[N]; ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { cin >> n >> m >> str + 1; p[0] = 1; for (int i = 1; str[i]; ++i) { p[i] = p[i - 1] * mod; h[i] = h[i - 1] * mod + str[i]; } while (m --) { int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; if(get(l1, r1) == get(l2, r2)) puts("Yes"); else puts("No"); } return 0; }