把一段字符串变成一个数字——预处理一次前缀哈希，之后任意子串是否相同，都能在 O(1) 时间内比较。
判断两个字符串是否相等，最直接的办法是逐个字符比较，时间复杂度 O(长度)。如果需要反复比较很多对子串是否相同（比如"字符串里有没有某个子串重复出现过"），每次比较都要 O(长度)，次数一多，总时间会很可观。
字符串哈希的思路是：把每个字符串（或子串）都映射成一个数字，只要提前预处理好，之后比较两个子串是否相等，就只需要比较两个数字是否相等——O(1) 完成。
把字符串看成一个"很多位"的数字，每个字符的（ASCII）值当作这一位上的"数字"，选一个底数 base（类似十进制的 10，二进制的 2），字符串 s[1..n] 的哈希值定义为：
hash(s) = ( s[1]×basen-1 + s[2]×basen-2 + ... + s[n]×base0 ) mod M
和十进制数 "123" 等于 1×10²+2×10¹+3×10⁰ 是同一个道理，只是把"进制"从 10 换成了自定义的 base，把"数字 0~9"换成了字符的值。为了让这个数字不会大到存不下，还要对一个较大的数 M 取模。
用字符串 s = "abcab" 演示（a=1, b=2, c=3，为了方便手算，这里取 base=31，M=97——实际竞赛代码会用大得多的质数作为 M，这里只是为了让计算过程看得清楚）：
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| h[i] | 0 | 1 | 33 | 56 | 88 | 14 |
h[i] 是"前 i 个字符"（也就是 s[1..i]）这段前缀的哈希值。比如 h[2] = (h[1]×31 + s[2]) mod 97 = (1×31+2) mod 97 = 33，对应前缀 "ab"。这个数组只需要正序扫一遍字符串，O(n) 就能预处理完。有了前缀哈希数组，任意子串 s[l..r] 的哈希值可以 O(1) 算出来，不需要重新扫一遍：
hash(s[l..r]) = ( h[r] - h[l-1] × baser-l+1 ) mod M
直觉上，h[l-1] 是"前 l-1 个字符"的哈希，要先把它"移到和 h[r] 同样的位数"（乘以 base 的 r-l+1 次方，相当于在末尾补上 r-l+1 个 0），再用 h[r] 减掉这部分"多余的前缀"，剩下的正是 s[l..r] 这一段的贡献。
拿 s = "abcab" 验证一下：s[1..2] = "ab" 和 s[4..5] = "ab" 内容相同，哈希值应该相等：
| 子串 | 计算过程 | 结果 |
|---|---|---|
| s[1..2] = "ab" | h[2] - h[0]×base² = 33 - 0×88 | 33 |
| s[4..5] = "ab" | h[5] - h[3]×base² = 14 - 56×88 = 14 - 78 | 33（对 97 取模后） |
"ab" 这两处内容完全一致的事实吻合——不需要逐字符比较，只靠两个 O(1) 算出的数字，就能确认这两段子串相同。| 1 | const int BASE = 131; |
| 2 | const long long MOD = 1000000007; |
| 3 | long long h[MAXN], pw[MAXN]; // h：前缀哈希；pw：base 的幂次表 |
| 4 | |
| 5 | void BuildHash(const string& s) |
| 6 | { |
| 7 | int n = s.size(); |
| 8 | h[0] = 0; pw[0] = 1; |
| 9 | for (int i = 1; i <= n; i++) |
| 10 | { |
| 11 | h[i] = (h[i-1] * BASE + s[i-1]) % MOD; // ★ s 下标从 0 开始，s[i-1] 对应第 i 个字符 |
| 12 | pw[i] = pw[i-1] * BASE % MOD; // ★ 预处理幂次，Query 时直接查表 |
| 13 | } |
| 14 | } |
| 15 | |
| 16 | // 查询 s[l..r] 的哈希值（l, r 从 1 开始，闭区间） |
| 17 | long long GetHash(int l, int r) |
| 18 | { |
| 19 | return ((h[r] - h[l-1] * pw[r-l+1]) % MOD + MOD) % MOD; // ★ +MOD 防止负数，见 ⑥ 陷阱 |
| 20 | } |
h[] 是前缀哈希，pw[] 是提前算好的 base 幂次表——避免每次查询都重新用快速幂计算 base 的幂次（那样会让每次查询退化成 O(log n)）。BuildHash 跑一次 O(n)，之后 GetHash 每次都是常数时间。MOD 选得越大，碰撞概率越低，但永远无法完全消除。竞赛中如果需要更高的正确性保证，常用双哈希：同时用两组不同的 (BASE, MOD) 各算一遍，两组哈希值都相同才认为两个字符串相等，能把碰撞概率降到极低。h[r] - h[l-1]*pw[...] 在取模的世界里，结果可能是负数（C++ 里负数取模的结果也是负的），如果不做处理，后续比较哈希值时会出问题。代码里 (... % MOD + MOD) % MOD 这个写法，就是先加一个 MOD 再取模，确保结果落在 [0, MOD) 的正确范围内。BASE 和 MOD 选得不合适：BASE 通常选一个比字符集大小更大的质数（比如 131、13331），MOD 选一个大质数（比如 10⁹+7）。如果 BASE 太小或者和字符集大小有公因数、MOD 不是质数，都会提高哈希冲突的概率，在精心构造的测试数据面前更容易被"卡掉"。