字符串哈希
字符串 Hashψ(｀∇´)ψ
思想和 Hash 没有本质区别。
要关注的点依旧是怎么设计 Hash function，怎么处理 Hash 冲突。
考虑把一个字符串映射成一个数，这个利用 Hash function 即可。
一个需要注意的点是 Hash function 需要满足以下两个条件：
-
在 Hash 函数值不一样的时候，两个字符串一定不一样；
-
在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。
Hash 函数值一样时原字符串却不一样的情况叫做哈希冲突。
做法是，我们选取一个大质数 \(base\)，然后把字符串看做一个 \(base\) 进制数，算出这个值之后对另外一个大质数 \(mod\) 取模。
不过其实 \(base\) 只需要大于字符集大小即可，注意一般 \(base < mod\)。
也就是说，对于一个长度为 \(n\) 的字符串 \(s\)，（从 \(1\) 开始）它的 Hash 值是这样计算的：
然后这个东西也可以很方便的支持基本的字符串操作。
比如 \(H(s + ch) = (H(s) \times b + idx(ch)) \% mod\)，\(ch\) 是一个字符，有点类似于位运算的左移运算。
然后减去一个字符或者在开头加字符也类似（当成 \(base\) 进制数即可）
不过减去的时候记得要加上 \(mod\) 免得寄掉。
如果是在中间修改的话就直接找到对应位置减掉就行了。
然后有这个东西我们就可以快速求出一个字符串所有前缀的 Hash 值。
有了前缀 Hash，我们想干的一件事情就是快速求出子串的 Hash。
推一下式子，显然可以发现：\(H(s[l\dots r]) = H(s[1\dots r]) - H(s[1\dots l - 1]) \times base^{r - l + 1}\)，记得取模。
然后就能 \(O(n)\) 预处理 \(H, base^n\) 之后 \(O(1)\) 询问子串 Hash 了，当然 \(base^n\) 也是可以快速幂算的。
注意到这样单次 Hash 的冲突概率还是有点小小的高，所以为了正确性，我们可以取两个大质数分别取模，然后两个字符串相等当且仅当两个 Hash 值都相等。
为了降低冲突概率，我们一般使用一对孪生素数，一般是 \(10^9 + 7, 10^9 + 9\)，当然这个比较容易被卡（因为过于著名）。
所以可以使用其他的素数对，比如 \(998244853,10^9+9\) 这种，\(base\) 一般取 \(131, 13331\) 这种。
如果想避免过多的取模，可以使用 ull 存 Hash 值，直接不做任何取模，这样相当于对 \(2^{64}\) 取模（自然溢出法）
应用 & 例题ψ(｀∇´)ψ
字符串匹配ψ(｀∇´)ψ
单模式匹配，直接考虑对于模式串求出它的 Hash 值，然后扫描文本串的所有和模式串长度相等的子串看是否能匹配就行。
复杂度 \(O(n)\)。
最长回文子串ψ(｀∇´)ψ
考虑一个经典 Trick，因为回文串的长度显然具有单调性，如果 \(len\) 长度的可行，那么 \(len - 2\) 的必然可行。
所以考虑二分答案 \(len\)，每次 Check 的时候直接枚举回文中心，比较两边这两个子串的 Hash 值是否相等即可。
需要预处理前后缀 Hash 值，整体复杂度 \(O(n \log n)\)。
这个也可以 Manacher \(O(n)\) 做。
最长公共子串ψ(｀∇´)ψ
这里是 \(m\) 个长度不超过 \(n\) 的字符串求。
这个类似回文子串也可以二分。
check 直接对于所有长度为 \(mid\) 的子串，Hash 一下分别扔到 \(n\) 个 Hash table 里面求交集就行，复杂度 \(O(n\log n/m)\)，目前不太懂为啥是这个复杂度。
但是它确实比直接 \(O(n^2)\) dp 效率高。
本质不同子串个数ψ(｀∇´)ψ
这个好像只能 \(n^2\) 左右复杂度 /ng
做法就是直接扫一次每个子串，然后把它的 Hash 值扔到一个数组/set里计数就行。
其本质就是对暴力做了一个优化，有没有更优秀的做法我暂时不知道。
CF1200E Compress Wordsψ(｀∇´)ψ
给你 \(n\) 个字符串，答案串初始为空。第 \(i\) 步将第 \(i\) 个字符串加到答案串的后面， 但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 \(i\) 个串的前缀的字符串），求最后得到的字符串。 \(n \le 1e5, \sum len \le 1e6\)。
直接考虑暴力合并，每次二分这个要被合并掉的串的长度，然后每次合并前预处理前后缀 Hash。
于是 Check 就变成了 \(O(1)\) 的，就可以 \(O(\log n)\) 找出这个串，之后把合并进来的串去掉公共串的部分找出来加到答案串后面即可。
复杂度 \(O(n \log n)\)，这题也可以 KMP 做，因为这个最长相等前后缀和 Next 的定义是一致的。