扩展kmp
最开始根本静不下心来看讲解，只是看了一些皮毛，后来多看了几遍大概才懂的，简略的写下笔记吧。
比如给出一个串[abcabcabc],ext[9,0,0,6,?,?,?,?,?]，不算第一个，那么我们求到的最远的那个p为9，使得p最远的那个位置叫做pos，p=pos+ext[pos]-1,pos=4.
现在考虑5这个位置，因为之前我们已经知道s[4..9]=s[1..6],那么显然s[5..9]=s[2..6],于是我们去拿到2的ext来看一看。
(1)ext[2]==0<=(9-4+1),说明之前已经失配过了，则直接把它的ext搬过来就行了。
(2)如果ext[2]>(9-4+1),说明我现在这个位置的ext是有可能增长的，p后面信息未知，那么就去匹配p后面的，直到失配位置，并且更新那个最远的pos和p。
拿其他的串来匹配这个串的前缀是一样的道理，我其实最开始是因为想到两个串怎么匹配所以才满满开始思考一个串怎么求ext的。
然而这种东西明显可以二分hash搞嘛，如果考场上遇到了写对的正确性也很低昂，二分hash虽然多一个log但是好写嘛，应该不会有专门考扩展kmp然后来卡二分hash的东西吧。
但是思想至少是理解了的，实现还是感觉很麻烦，如果真心考这个只有gg了。
//据红布学长透露他的OI生涯中从来没遇到扩展kmp，ovo那我就放心啦。