KMP算法next数组

next数组规则如下：

注意，下标j从1开始，到最后一个字符结束（当然也可以是0，只要所有的值都减1即可）

1. next[j] = 1 , j = 1
2. 满足如下条件的k的最大值：

n e x t [ j ] = { m a x ( k ) ∣ 1 < k < j , p 1 . . . p k − 1 = p j − k + 1 . . . p j − 1 } 。 其中 0 < p 1 ≤ p k − 1 , 0 < p j − k + 1 ≤ p j − 1 。 next[j] = \{max(k) \quad | 1next[j]={max(k)∣1<k<j,p1​...pk−1​=pj−k+1​...pj−1​}。其中0<p1​≤pk−1​,0<pj−k+1​≤pj−1​。

3. next[j] = 1，其他情况

比如字符串"abaabcac"的next数组为：111223121

至于改进的next数组，情况将会更加复杂，暂不赘述。

卡特兰数：

$$\frac{C_{2n}^n}{n+1}$$