简介：字符串算法总结，包含哈希，trie，KMP，AC自动机，后缀数组，后缀自动机，manacher，回文自动机等
把字符串按照顺序每一位赋一个值并求和，即将字符串视为一个 n进制 的数
通过预处理前缀和以及所有的 \(n^k\) 的值，即可快速算出 \([l,r]\) 区间内的子串的哈希值
常用于判断两个子串是否相同
注意哈希可能发生冲突，即两个不同字符串的哈希值相同
比较好的方式是双取模哈希，即对两个不同的模数计算子串哈希值，极难出错（目前bzoj上似乎还没有人叉掉双模哈希）
但是由于上述方式常数较大，当字符串长度较小或字符集大小很小时常采用自然溢出，即使用 unsigned long long 保存哈希值并不手动取模（等价于对 \(2^{64}\) 取模）
有时也会采用单模数哈希（使用哪个一般看心情？）
trie 是一个有根树形结构，其中每个节点代表一个字符串，每条边代表一个字符。
每个节点代表的字符串即为从根到这个节点的路径上的字符顺次拼成的字符串
trie 的构建十分简单，在插入一个字符串的时候，就从根出发，每次走对应字符的边，如果没有这条边就新建一条边并走下去
一般配合自动机使用，偶尔有 trie 上直接 dfs 或 dp 的题
KMP 是一个字符串匹配算法（或许是简单算法中较难理解的一个？）
KMP 用于处理一个串在另一个串中作为子串出现的次数以及位置的问题，复杂度为 \(\Theta(n+m)\)
具体实现：考虑使用两个指针，分别表示当前母串和匹配串各匹配到了哪个位置，那么如果下一位相同，显然两个指针同时右移，否则匹配串的指针得向前移动
如果我们暴力寻找下一个位置，复杂度为 \(\Theta(nm)\)，无法接受。但是我们发现，假设当前的匹配串的指针为 \(p\)，那么我们已知了母串的后 \(p\) 位和匹配串的前 \(p\) 位，这样可以预处理。
所以我们考虑预处理匹配串的前 \(p\) 个字符匹配上了，第 \(p+1\) 个字符失配时下一次可以从匹配串的哪里开始继续匹配，即匹配串的前缀和其前 \(p\) 个字符的后缀相同的最长长度。令前述为 fail[p]，不难发现 fail[p] = fail[...fail[fail[p - 1]]] 直到某个位置满足其下一位的字符正好是 s[p]，如果不存在这样的位置那么 fail[p] = -1。
那么我们求出了 fail 数组后匹配过程十分简单，当第 \(i\) 位失配的的时候，i = nxt[i - 1] + 1 即可
原文：https://www.cnblogs.com/wawawa8/p/10987411.html