江湖中，剑客以快制胜，而算法竞赛里，字符串哈希（String Hashing）便是那柄出招如电的快剑。
各种字符串问题纷乱复杂，各种字符串算法招式繁复，需苦练内功心法。但字符串哈希算法却只凭一招：将字符串化作数字，以数论为刃，至简之道斩尽来犯之敌。
但此招并非无懈可击。若遇精心构造的数据，它可能一剑刺空，露出破绽。然而，在绝大多数情况，它仍是侠客们最趁手的兵器——七分准，三分险，却快得让人无从招架。
何为进制哈希？
哈希是复杂对象到较小整数的映射，而进制版本的字符串哈希是一种很有趣的哈希方式。他把字符串转化为一个b进制的数值。
例如，字符串 "ab"：
- 若设 u=1, v=2，取 base=131（进制基数），则其哈希值为：
\[H('uv') = 1 \times 131^1 + 2 \times 131^0 = 133\]
既然是将字符视为数，那每个字符需要一个值，同时还需要一个进制大小。
考虑字符集（Character Set），一般就使用字符的编码即可（如 ascii 或 unicode），简单起见本文只考虑小写字母集：a-z（26个字符），对应1-26
注：为什么不使用0-25？因为把 0 放入编码，会导致出现"a"和"aa"相等，"aaabcd"和"aaaaabcd"相等的情况，太容易构造冲突。为了应对构造数据，不如直接使用 ascii 本身，或者至少让a-z（26个字符），对应1-26。
考虑基数（Base）的选择，基数显然至少大于字符集大小。若用a-z，26字符去除 0，需要 27进制，实际上也可以更大，常用质数基数：131、13331 等。
随着字符串长度增加，这个数迅速就变得非常大，所以要再对某个大质数取模，便得到最终的编码。
查询子串哈希
字符串哈希之所以是"快剑"，因为它有一个奇妙的性质：它能通过前缀哈希（Prefix Hash），在 O(1) 时间内斩出任意子串的哈希值。
选定编码和基数后，我们处理出a：存储前 s[0..i] 的哈希值，显然有秦九韶算法：a = a[i-1] * base + d;
现在我们要计算子串s[l..r]的哈希，其原理如同在进制数中取数：
- 将前缀哈希a[r]视为大数。
- 减去a[l-1]向左位移(r-l+1)位的干扰（通过乘p[r-l+1]实现，p为基数的幂次）
[code]// 为了简单和效率，直接选用 unsigned long long，模数等价于2^64，称为自然溢出。class hashstr { using u64 = unsigned long long; int n; u64 mod; vector a, p; const static int base = 131;public: hashstr(const string &s, u64 mod = 0): n(s.size()), a(n), p(n+1) { u64 x = 0; for (int i = 0; i < n; ++i) { int d = s; // ASCII a = x * base + d; } p[0] = 1; for (int i = 1; i |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
