kmp算法next计算方法

KMP算法是一种字符串匹配算法，其中next数组的计算是其核心之一。next数组表示当模式串中出现不匹配时，模式串应该从哪个位置开始重新匹配。其计算方法如下：

1. 初始化：令next[0] = -1，i = 0，j = -1；

2. 计算next[i]：

- 若j = -1或p[i] = p[j]，则next[++i] = ++j；

- 否则，令j = next[j]，并重复步骤2。

3. 返回next数组。

其中，p为模式串，i为当前计算的next值所对应的下标，j为当前已经匹配的字符数。

需要注意的是，KMP算法的next数组从1开始存储，而不是0。