KMP算法中的next数组详解

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。其中，KMP算法的关键在于求解模式串P的next数组。下面详细介绍next数组的含义、求解方法以及应用。

1. 含义

next数组是一个长度为m（m为模式串P的长度）的数组，其中next[i]表示P[0:i]这个子串中，最长的既是其前缀又是其后缀的字符串的长度。特别地，next[0]=-1，next[1]=0。例如，当P="abab"时，其next数组为[-1,0,0,1]。

2. 求解

next数组的求解可以通过动态规划的方式实现。具体来说，在求解next[i]时，假设已知next[0:i-1]的值，我们需要找到一个最长的既是P[0:i-1]的前缀，也是P[1:i]的后缀的字符串。这个字符串可以通过比较P[0:j-1]和P[i-j:i-1]来得到，其中j=next[i-1]+1。

如果P[j]==P[i]，那么next[i]=j；否则，我们需要找到一个更短的字符串。此时，我们可以利用next数组的性质，从next[j]开始向前查找，直到找到一个P[k]等于P[i]为止，然后令next[i]=k。如果一直找到k=-1还没有找到，那么next[i]=0。

3. 应用

有了next数组之后，我们就可以利用KMP算法在文本串S中查找模式串P的出现位置。具体来说，我们维护两个指针i和j，分别指向S和P的当前位置。如果P[j]==S[i]，那么i和j都向后移动一位；否则，我们利用next数组来决定j的下一步移动位置。具体来说，如果next[j]=-1，或者next[j]<i，则令j=0，i不变；否则，令j=next[j]。这样，我们可以在O(n+m)的时间复杂度内完成匹配。