概述
对于统计 $S$ 在 $T$ 中的出现次数的问题。称 $S$ 为模板串，$T$ 为文本串。KMP 算法可以解决单模板串匹配问题。
先对模板串预处理 nxt 数组，代表 $[1,i]$ 的最长相等真前后缀的长度。也可以理解为在模板串上建立自动机。
然后遍历文本串进行匹配，时间复杂度均摊为 $O(n+m)$。
应用
最短循环节
最短循环节存在当且仅当 $(n-nxt_n) | n$，此时最短循环节长度为 $n-nxt_n$。
1.Prefix Function Queries
可以每次加入 $\text{t}$ 后从 $\text{t}$ 开始跑 KMP，但这样时间复杂度不对（因为时间复杂度是均摊的）。
可以对于 $\text{s}$ 预处理出从 $i$ 开始，与 $\text{c}$ 匹配跳 fail 最终跳到的节点，这样当 $p \le n$ 时就可以 $O(1)$ 转移了。
时间复杂度 $O(SZ|\text{s}| + \sum |\text{t}|)$。
用可持久化线段树可以优化至 $O(|\text{s}| \log SZ)$
2.[CERC2019] ABB
一个串最少加入 $n-最长回文后缀$ 个字符形成一个回文串。
求最长回文后缀可以求 $\overline{s} + “!” + s$ 的 $border$
3.[POI2005] SZA-Template
印章一定是原串的一段前缀。
考虑 DP，记 $f_i$ 为 $[1,i]$ 需要的最短长度。
发现 $f_i$ 只有 $i$ 和 $f_{nxt_i}$ 两种取值。最起码要能覆盖 $[1,nxt_i]$，再多了就不能覆盖 $[i-nxt_i+1,i]$ 了。
只有当 $[i-nxt_i,i]$ 中存在 $j$ 使得 $f_j = f_{nxt_i}$ 时，$f_i$ 才取 $f_{nxt_i}$。用个桶记录最大位置。
4.【模板】失配树
建出 $\text{fail}$ 树，找两个点父节点的 $\text{LCA}$。
5.[NOI2014] 动物园
建出失配树，维护 $f_{u}$ 表示 $u$ 的答案，每次对子节点取 $\min$ 再往上跳即可。最后答案为深度。
也可以维护一个栈，中间维护一个指针，个数即为指针的位置。