kmp模式匹配算法求next

KMP（Knuth-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串中查找给定的子串。它避免了在每次匹配失败后都从头开始搜索，而是利用了一个辅助数组`next`来存储模式串中的最长前后缀相等的长度，从而实现了一种“局部回退”的机制。

以下是KMP算法的主要步骤：

1. **构造next数组**：首先，为模式串计算next数组。这个数组表示当模式串在当前位置匹配失败时，需要跳过多少个字符才可能找到一个新的匹配点。next[i]的值等于i之前最长的前缀和后缀公共部分的长度，如果找不到这样的公共部分，则next[i] = 0。

2. **匹配过程**：在主串和模式串的比较过程中，如果当前字符不匹配，但模式串的下一个字符可以通过next数组确定其应该跳过的字符数，那么就将模式串向右移动next[current_char - pattern]个位置，继续比较。

3. **循环匹配**：重复上述步骤，直到模式串完全匹配到主串或模式串遍历完为止。如果模式串完全匹配，返回匹配的位置；否则返回-1表示未找到匹配。