张华清 字符串 学习笔记
Hash
问题描述
快速比较两个字符串是否相同。
具体来说，求一个字符串 s 到整数的映射 hash(s)。
思路
-
若
s1=s2，则hash(s1)必等于hash(s2)； -
若
hash(s1)=hash(s2)，我们认为s1有极大概率=s2。通过预处理给每个字符串一个特征值。
实现
-
Hash 函数
把字符串当成一个 \(b\) 进制数（\(b \leq\) 字符集大小），然后模 \(p\)（\(p\) 一般为大质数）。 -
单模 Hash
一般 \(p\) 取一个 \(1e9\) 级别的大质数。- 当 \(n\) 为 \(1e5\) 左右时几乎一定会炸。
- “生日悖论”。
-
自然溢出 Hash
用unsigned long long，自动对 \(2^{64}\) 取模。
优点：- 足够大，不容易炸；
- 可以卡，但一般不会被卡；
- 快。
-
双模 Hash
- 同时取两个模数，值域变成 \(p1 × p2\)，不会炸；
- 可以一个大质数，一个自然溢出；
- but 会慢 and 难写。
细节注意
- \(b\) 要大于字符集的大小;
- 不要把字符映射到 \(0\);
例题：子串 Hash
-
题目描述
给定一个长度为 \(n\) 的字符串 \(s\)，希望通过 \(O(n)\) 的预处理后，\(O(1)\) 询问某个子串的 \(Hash\) 值。其中子串必须是连续的。 -
做法
令 \(f_i\) 为 \(s_i\) 的 \(Hash\) 值，可以通过递推求出：\(f_i=f_{i-1} × b+s_i\)。
如果求 \(s_l ~ s_r\) 的 \(Hash\) 值，就是：\(f_r-f_{l-1} × b ^ {r-l+1}\)，注意要提前预处理出 \(b\) 的各个次方。