**什么是Next数组？**
KMP算法通过创建一个“失配指针”来优化传统暴力搜索方式，在遇到不匹配字符时无需回溯已比较过的位置。这个优化的关键数据结构就是所谓的"Next数组"或者说 "Partial Match Table"（局部匹配表）。对于给定的目标模式P[0...M-1]，它的Next[i]值表示当以 P[0…i-1] 为前缀的部分进行最长有效前后缀匹配后，下一个应该对齐到主文本上的位置索引。
例如：若目标模式是 `ABCDABC` ，则对应的Next数组可能是 `[0, 0, 0, 1, 2, 3, 4]` 。这意味着：
- 对于第一个元素A，没有更短的有效相同前后缀；
- 当遍历至B、C甚至D的时候同样如此，因为在这三个长度的连续序列里不存在相同的非空前后缀；
- 到了第四个元素（即第二个'A'），它前面有长度为1的一个相同前后缀"A";
- 同理可得后面的数值对应关系...
**如何构建Next数组?**
构建Next数组的过程可以采用动态规划的方式逐步求解每个状态的转移结果：
markdown
初始化：
next[0]=-1
循环主体:
遍历 i=1 至 M-1 （其中M为目标模式长度）
如果 pattern[i]==pattern[next[i - 1]] //当前字符与其之前的最大相等前后缀结尾字符相同，则扩展此最大相等前后缀。
next[i]=next[i - 1]+1;
否则
j = next[i - 1]; // 回退并尝试找到新的最长大约束条件下的相等前后缀
while(j > -1 && pattern[j]!=pattern[i])
j = next[j];
next[i] = j + 1; // 更新next[i]
以上过程确保每次迭代都记录下当前位置之前的最长具有公共前后缀性质的子串长度，从而避免无效重复对比，并显著提升搜索效率。
总结来说，Next数组作为KMP算法的重要组成部分，通过对原问题分解并在有限空间内预先存储可能的状态转换情况实现了快速高效的子串定位功能，极大提升了相关应用场景如文件检索、文档查重等方面的性能表现。