KMP小结
前言
今天临时起意想清一下自己的刷题计划。就发现了一道很典但是我不会的 kmp，所以就想写一下我对 kmp 的理解。所以基本上是自己在乱 B。
联赛前应该不会再 kmp 了。
如果退役了的话，这辈子都不会 kmp 了。
kmp
kmp 的 $nex_i$ 本质上是在维护以 $i$ 结尾的 border 集合中最大的 border。因为 border 集合中 border 都是依次被更大的包含，所以也只需要维护最大的 border。
复杂度来看，每次最多只会加入一个 border，不管删除多少，所以复杂度是均摊 $O(n)$。
失配树
这个板题就是把 border 建一棵树，公共 border 就是他们的共同祖先。最大的就是最近公共祖先。
不太懂和失配什么关系。
例题：[POI2005] SZA-Template
删除
一般来说，kmp 的删除是隐性的，因为我们只需要最大的 border，所以根本不用管删除那些小的 border。
但如果我们想要维护这个 border 集合，就要快速找到要删除的 border。具体维护看下面的例题。