失配

[传送门](https://www.luogu.com.cn/problem/P5829) 考虑把原字符串先$kmp$一遍，求出以$i$结尾的前缀的最长$border$，根据$border$的$border$还是$border$这个定理，我们在寻找前缀$p$和前缀$q$的最长公共$border$时， ......

又叫做 fail 樹。可愛捏（（（ 用於求解字符串兩個前綴的最大公共 border。 我們先跑一邊 KMP 算法求出 $nxt[]$ 數組。 我們連出每一個邊 $(nxt[i],i)$，嗯嗯為此我們需要新建一個 $0$ 點。 那這個樹有什麼性質捏，顯然一個節點的祖先都是祂的 border。 額大家都 ......

## 1.kmp 这就不讲了吧，border数组弄懂就是水算法了！~~但是变种真的毒瘤啊~~ ## 2.hash emmmmm ## 3.fail树 这就是kmp的border数组的变种 kmp一次一次next跳，太慢了！ 我们就想到倍增优化嘛 $n$个点，$n-1$ 条边 联通 一眼顶针这就是一颗 ......