数据结构kmp算法 next数组

KMP算法是一种字符串匹配算法，用于在一个主串S内查找一个模式串P的出现位置。其中next数组是KMP算法的核心部分，它存储了每个前缀和后缀的最长公共部分长度。

具体来说，假设在主串S中找到了一个与模式串P的前k个字符相同的子串，但是第k+1个字符不匹配，那么我们可以利用next数组，将模式串P向右移动j-next[j]个位置，继续与主串S中的第k+1个字符进行匹配，其中j为当前已匹配的字符数。

下面是next数组的求解过程：
1. 初始化next = -1，next = 0；
2. k表示当前已匹配的字符数，j表示当前正在匹配的字符数；
3. 如果P[k] == P[j]，那么next[j+1] = k+1，并且将k和j都加1；
4. 否则，令k = next[k]，如果k == -1，则令next[j+1] = 0，并且将j加1；
5. 重复步骤3和步骤4，直到j等于模式串P的长度。