kmp中的next数组

KMP算法（Knuth-Morris-Pratt 算法）是一种用于字符串匹配的高效算法，它通过预处理模式串（也称为文本串），生成了一个叫做“next数组”的辅助数据结构。next数组的作用是在搜索过程中避免回溯。

对于模式串中的每个字符i（从第二个字符开始），next[i]表示在模式串中最长的前缀与前缀加字符i相等的最长公共长度。简单来说：

- next[0] = 0，因为前缀长度为0时，没有其他相同的前缀。
- 如果模式串的第一个字符和当前字符匹配（即text[prefix+1] == pattern[i]），那么next[i] = next[prefix] + 1，意味着找到一个新的相等的前缀长度。
- 如果不匹配，则尝试跳过一些已知不匹配的字符，查找下一个潜在匹配的位置。例如，如果pattern[i] != text[j]且next[k] (k < i) 最大化了 prefix+k 和 i 的相等部分，那么next[i] = next[k] + 1，表明我们回到前面已经检查过的某个位置继续比较。

通过这种方式，当遇到不匹配的情况时，KMP算法能够利用next数组直接定位到可以继续比较的位置，而不是从头开始，大大提高了匹配效率。