字符串那些东西

总结一些从简单到困难的字符串算法，基本什么都有。不过自己对哈希和 Trie 掌握的还可以所以没有总结。

这并不是一个从零开始讲的题解，而是在已经学会算法的基础上加深理解，所以并不适合萌新qwq。~~因为是给自己复习用的所以讲的很烂也不适合别人看。~~

前缀函数和KMP

前缀函数的定义：子串最长的相等的真前缀与真后缀的长度。
OI-wiki 上有 "特别地，规定 $\pi[0]=0$ "，然而有时候得具体分析（比如说求 $Z[0]$ 的时候）

"KMP算法"求前缀函数

~~其实准确来说应该是求前缀函数算法，因为KMP是前缀函数求字符串匹配的应用~~

核心思想是：在扩展的时候，尝试用上一层的答案匹配，如果失配的话跳上上层的答案（ $pi_{i-1}$ ）。

之所以用上一次的答案匹配是因为，如果 $j$ 的上一层 $i$ 的答案已经保证了 $1 \sim pi_i = j-pi_i \sim j-1$，所以我们只需要 $pi_i+1 = j$ 就行了。如果上一层的答案失配了呢？就不断找上一层答案的上一层答案，也就是 $pi_{i-1}$

这个找上上层答案的正确性在于前缀函数的定义就是相等，举例来说， $ABC$ 三个字母表示一个子串的话，有：字符串 $CABCABC$。第一层前缀函数（ $pi_7$ ）保证了大的 $CABC$ 和 $CABC$ 相等，而 $CABC$ 内部的前缀函数（ $pi_4$ ）又有 $C_1 = C_4$，连起来就有 $C_1 = C_7$，构成了一个新的相等前后缀，可以扩展答案（尽管这个例子中它没有任何作用）

对 $pi$ 进行简单势能分析（单次最多加一）可以得到复杂度 $O(n)$

真正的KMP算法求字符串匹配

前缀函数可以用于求字符串匹配，你可以从它的定义的角度把他当成一个匹配的工具使用，不过咱有个更简单的理解。

用一个不会出现的分割符把模式串和文本串连接起来，求前缀数组，根据定义当前缀数组的长度刚好为模式串长度的时候，说明成功匹配了（找到的这个位置是匹配的末尾）

多个文本串的话，可以提前把模式串的前缀数组求出来，因为求前缀函数是在线的所以无需担心要多次计算模式串的前缀数组导致 TLE。

前缀函数求循环节

结论是循环节长度为 $n - pi_n$，其实非常好理解，画个图马上出来。

  A B C D 
A B C D

因为前缀函数表示相同，$ABCD = ABCD$，所以有 $A=B,B=C,C=D$ ，容易得出循环节就是 $A$ 的长度，也就是 $n-pi_n$。

前缀函数求每个前缀的出现次数

首先一个蛮重要的小结论： 如果对 $i$ 向 $pi_i$ 连边，会得到一颗树，每个节点表示的是一个前缀在整个串的子串中以后缀的形式出现了一次（其实也就是在串中出现了一次）。$u$ 向 $v$ 连边表示 $v$ 是 $u$ 的前缀。

然后另外一个更简单的小结论，一个前缀出现了，它的前缀也出现了一次（前缀的前缀还是前缀）。

所以结合起来，每个前缀的答案要对它的前缀的答案产生累加的贡献。我们当然可以树形DP或者拓扑排序，然而因为有 $pi_i \le i$，所以可以直接逆序求解。以下代码来自 OI-wiki，侵删。

vector<int> ans(n + 1);
for (int i = 0; i < n; i++) ans[pi[i]]++;
for (int i = n - 1; i > 0; i--) ans[pi[i - 1]] += ans[i];
for (int i = 0; i <= n; i++) ans[i]++;

最后一句话的意思是，前缀自己也以前缀的身份出现了一遍（这肯定不算一个子串的真后缀，所以没有被统计过）