next 树
可以说 KMP 算法的精髓就在于失配时通过 next 指针快速重新匹配。对于字符串中的第 $i$ 个位置，$\text{next}_i$ 的意义是 $s[1,i]$ 中除本身之外的同时为其前后缀的子串的最大长度。
[NOI2014] 动物园
对于一字符串，定义 $\text{num}_i$ 为其同时为不相交的前后缀的子串的最大长度。
给定一长度为 $n$ 的字符串 $s$ , 求 $\prod_{i=1}^n\text{num}_i+1$
$T\leq5,n\leq10^6$
这道题目中的 num 数组其实是对 KMP 中的 next 数组的条件进行了限制，也就是说某些符合 next 数组的子串可能因为进一步的限制（不能重合）而不再适用。很明显的是：某个位置不断沿着失配指针走，所经过的每个位置都满足“除本身之外的同时为其前后缀的子串”的限制，而为了保证其不能重合，只要这一子串的长度不大于原串长度的一半即可。
容易想到将 next 指针看成边，那么所有的指针就形成了一棵以 $0$ 号节点为根的树。
我们在这棵树上 dfs , 用一个 stack 记录当前节点到根的路径信息，然后在上面二分即可得到答案。
逆向模拟 KMP 算法
字符串大师
一个串 $T$ 是 $S$ 的循环节，当且仅当存在正整数 $k$ ，使得 $S$ 是 $T$ 重复 $k$ 次的字符串的前缀。给定一个长度为 $n$ 的仅由小写字符构成的字符串 $s$ ，对于字符串 $s$ 中的每一个前缀 $i$, 给出其最短循环串的长度 $\text{per}_i$ , 求满足条件的字典序最小的字符串。
$n\leq10^5$
发现所谓的 $\text{per}_i$ 其实与 $\text{next}_i$ 有关，即 $\text{per}_i=i-\text{next}_i$ , 于是就可以求出要求的串的 next 数组。
那么问题就变成给定 next 数组还原出字典序最小的字符串，考虑两种情况：
- $\text{next}_i=0$ , 根据充分性要求，$i-1$ 位置上以及其所有先前的匹配位置上的字符与此处不同。
- $\text{next}_i\neq0$ , 根据必要性要求，此处的字符必须与 $\text{next}_i$ 处的相同。
时间复杂度 $O(\sigma n),\sigma\text{ 为字符集大小}$