kmp算法的next数组图解

KMP算法（Knuth-Morris-Pratt 算法），是一种用于字符串匹配的高效算法。它通过构建一个“next”数组来帮助搜索过程，减少不必要的比较次数。这个数组主要用于存储模式串的前缀函数值，也就是在模式串中每个位置之前有多少个相同的前缀。

"next"数组的构造过程可以这样理解：

1. 初始化：对于第一个字符，其`next`值总是0，因为没有任何前缀。从第二个字符开始，`next[i]`表示最长的公共前后缀的长度，如果`pattern[i]`等于`text[prefix[i]+1]`，则`next[i] = next[prefix[i]] + 1`；否则，寻找一个比`next[i]`更大的值j，使得`pattern[j] == pattern[i]`并且`prefix[j] < prefix[i]`，即在之前的公共前后缀基础上添加`pattern[j]`到当前位置仍然匹配，将`next[i]`设置为`j`。

2. 图解示例：想象模式串`pattern`为`ABABCABD`，文本串`text`为`ABCDABABCAB`。首先计算`next`数组，如`next = 0`, `next = 0`, `next = 0`（因为前两个都是空）。当`i=3`时，`pattern`不等于`text[next+1]`，所以我们检查`pattern`是否等于`text[next[2]+1]`，发现也不匹配，然后继续向左移动找到`pattern == text[next+1]`，因此`next = 1`。如此往复，直至完整构建起`next`数组。

有了`next`数组后，实际匹配过程中，如果在文本中某个位置发生了错误的前缀匹配（比如找到了一个`B`而不是期望的`A`），我们就可以利用`next`数组快速跳过已经匹配的部分，提高查找效率。