初级字符串算法合集，预计内容包括：哈希、trie、kmp、manacher、z函数。
缓慢填坑。
哈希
哈希的分析
哈希实际上就是指把一个什么东西映射到一个比较小的值域上，设哈希函数为 $f(x)$，如果 $x=y$ 那么一定有 $f(x)=f(y)$，反之不一定成立。
字符串哈希一般使用多项式哈希，选定一个底数 $b$ 和一个模数 $p$，$f(s)=\sum_{i=1}^{len}s_i\times b^{len-i}\pmod p$
底数一般选择大于值域的任意数，可以认为 $f(s),f(t)$ 冲突的概率大概为 $\dfrac{len-1}{p}$。
计算总哈希冲突概率是很简单的，如果发现冲突概率不低，可以对两个质数分别取模，相当于值域扩大到两者之积，大大减少冲突概率。
因为取模常数较大，如果条件允许，也可以使用自然溢出（即对 $2^{64}$ 取模），可以减小常数。
子串哈希
类似前缀和的思想，不难得到：$f(l…r)=f(r)-f(l-1)\times b^{r-l+1}$，可以做到 $O(1)$ 回答子串哈希。
代码
使用自然溢出。
for (int i = 1; i <= n; i++)
hash[i] = hash[i - 1] * base + s[i];
ull gethash(int l, int r) { return hash[r] - hash[l - 1] * mi[r - l + 1]; }
应用
很多和字符串相关的东西都依赖于判断相等，经常可以二分+哈希在单个 $\log$ 的时间内解决。
trie
基本知识不说了，很简单。
异或问题经常可以用到 01trie。
各种 trie 都是支持合并的，类似线段树合并。
01trie可以维护不少有关异或的信息。
从低位到高位插入到trie中，通过维护一个点到其父亲这条边上被经过了几次可以轻松得到子树异或和，删除也可以这么做，还可以做到全局+/-1，以+1为例，只需要交换两个儿子，然后向0的那个儿子接着递归做即可。
kmp（前缀函数）
前缀函数 $nxt_i$ 定义为前缀 $i$ 最长的相等的前后缀长度。
求法就根据移动到下一个字符的时候，前缀函数要么不变、要么减小、要么增加 $1$，然后就往前跳求就可以了，因为总的增加是 $O(n)$，复杂度也就是 $O(n)$。
代码
下标从 $1$ 开始。
void get_nxt()
{
for (int i = 2, j = 0; i <= m; i++)
{
while (j > 0 && s[i] != s[j + 1])
j = nxt[j];
if (s[i] == s[j + 1])
j++;
nxt[i] = j;
}
}
应用
主要应用还是这个定义。
这里说一个方法：把字符串拼起来，可以正着拼、倒着拼、一个一个拼、中间加特殊字符等等，各种地方都能用的到。
应用——字符串匹配
讲一个无脑的方法，假如要求 $t$ 在 $s$ 中的匹配，那么可以把 $s$ 和 $t$ 拼起来，构造一个 $str=t+\#+s$，然后求 $str$ 的前缀函数，$\#$ 后面前缀函数等于 $|t|$ 就是一个匹配。
最长周期
border：对字符串 $s$ 和 $0<r< |s|$，若 $s$ 长度为 $r$ 的前缀和长度为 $r$ 的后缀相等，就称 $s$ 长度为 $r$ 的前缀是 $s$ 的 border。
由 $s$ 有长度为 $r$ 的 border 可以推导出 $|s| - r$ 是 $s$ 的周期。
故最长周期长度是 $|s| - nxt_n$
manacher
假如我们要求 $d_i$ 表示以 $i$ 为中心，最长的回文半径（这里暂不考虑一个回文串长度是偶数的情况）。
显然二分+哈希可以做到 $O(n\log n)$ 求解，但 manacher 算法让我们可以在线性时间内快速求出 $d$。
具体方法就是：维护当前右端点最靠右的回文串 $[l,r]$，对于一个新的点 $i$， 如果 $i\leq r$，那么把 $d_i$ 直接设置成 $\min\{r-i+1,d_{l+r-i}\}$，这样显然是正确的，而每次这么处理完之后，都暴力扩展 $d_i$ 并更新 $l,r$。复杂度为 $O(n)$，因为$r$ 从不减小。
对于长度为偶数的回文串，我们考虑在相邻两个字符间加一个其他字符，这样原串的一个偶回文串一定对应新串的一个奇回文串，问题得到解决。
代码
for (int i = 1, r = 0, l = 0; i <= n; i++)
{
if (i <= r)
d[i] = min(r - i + 1, d[l + r - i]);
while (s[i - d[i]] == s[i + d[i]])
d[i]++;
if (d[i] + i - 1 >= r)
r = d[i] + i - 1, l = i - d[i] + 1;
}