（由于字符串 hash 和整数 hash 是两个东西，以下将字符串 hash 称作 strash）
前情提要：
strash：我来！（非常好数据，使我的 strash WA 掉）
strash 是什么？strash 有什么用？该如何避免上述情况？
strash 是什么
strash 的原理其实很简单：
将一个字符串当作 \(b\) 进制数。
So you wrote a wrong code because of this
$\LARGE{b > |\Sigma|}$注意不是 \(\large{\ge}\)！
我的建议是第 \(i\) 个字符的位权为 \(b^{i - 1}\)（静态位权，方便维护）。
strash 有什么用
以下应用均不包含预处理 \(O(N)\) 时间。
\(O(1)\) 判断两个字符串相等
直接 strash 然后判断相等即可。
\(O(\log N)\) 判断两个字符串的字典序谁大谁小和求 LCP
二分 LCP，strash 判断相等，最后比较后面一个字符的大小。
同理还可以在 \(O(N \log N)\) 时间内判断某个字符串在另一个字符串中的出现位置（KMP：？？？）。
该如何避免“非常好数据，使我的 strash WA”
猜猜看，一个房间内至少有多少个人才能使得有至少 \(\dfrac{1}{2}\) 的 概率有两个人的生日相同（不考虑年份）？
答案其实令人惊讶：只需要 \(23\) 个。
所以，strash 的错误率还挺高的。
下面提供两种解决这个问题的方法（多选）：
-
开大模数。更大的模数会使你的失误率变得更小。
-
多重哈希。一个 strash 的失误率可能很大，但是如果你开到 5 个甚至 15 个，心力交瘁的就是 hacker 了。
最后，祝大家 for(;;){rp += LLONG_MAX;}！