KMP

next数组求解

next数组含义：next[i]表示i位置前最长的相同的前缀和后缀（前缀不能包括最后一个数，后缀不能包括第一个数）

next[0]规定为-1

假设在求next[i]的时候，i之前的next已经求出来了，那么过程如下：

根据这个我们就可以写出代码

pos是要求的当前的next的index

cn是要求pos时当前要考虑的next[cn]

可以证明复杂度是O(N)，思路与Manacher算法的证明思路是一样的，把循环的过程与某个变量进行绑定，如果变量在循环的过程中是不会减小的，而当变量达到某个值循环就会终止，那么我们就可以根据变量来推断复杂度，

具体对这个例子来说就是：pos 和 pos-cn，通过分析while循环的3个分支，可知这两个变量都不会减小，

第1个，第三个分支都是pos++，只有第二个分支是cn会减小，那复杂度还是不是O(N)呢？会不会在第二个分支运行很多次呢？答案是不会超过N次，因为每次选择第2分支，cn减小会导致pos-cn增大，而cn最小是0，所以pos-cn达到N是，pos这时必然大于N跳出循环。

所以三个分支无论走哪个，都会使pos 和 pos-cn中的一个增大，而pos到了N，或者pos-cn到了N都会跳出循环，所以总体时间复杂度O(2*N)