递推求kmp的next数组

KMP算法（Knuth-Morris-Pratt 算法）是一种用于字符串匹配的有效算法，其中next数组是一个核心的概念。它用于预计算模式串中的部分匹配信息，以便在主字符串搜索过程中跳过不必要的比较。

next数组的作用是在遇到不匹配字符时提供帮助。对于模式串中的每个位置i，next[i]表示当模式串从当前位置开始向右移动到下一个位置j时，如何调整模式串的位置，使得前缀仍然可以匹配。如果当前字符和前缀中的某个字符相等，那么next[i]就等于这个相等字符在前缀中的索引；若不等，则查找最长的前后公共前后缀（LPS, Longest Proper Prefix that is also a Suffix），即找到之前已计算出的next值对应的部分，然后加一。如果找不到这样的公共前缀，说明无法再向前移动，next[i]设置为0，表示从头开始匹配。

计算next数组的步骤如下：
1. 初始化：next = -1（模式的第一个字符没有前缀），然后next = 0（模式的第二个字符可以和第一个字符匹配）。
2. 从第三个字符开始遍历模式串，对于每个位置i，尝试找到最长的公共前后缀长度l，并更新next[i] = l。
3. 如果pattern[i] == pattern[l + 1]，则l自增并继续寻找；否则，尝试减小l，直到l >= next[l]，此时取l + 1作为新的匹配前缀。