**什么是Next数组？**
“Next数组”，也被称为前缀函数或失配表，在给定的主串P(Pattern)中，其定义为对于每个位置i (1 <= i < |P|)，记录的是以第i个字符结尾且最长相等前后缀长度的位置j(i ≤ j
例如：若有一个字符串 "ABCDABC"，则它的 Next 数组将是 [0, 0, 0, 1, 2, 3, 4]。
**如何计算Next数组?**
构建Next数组的过程是一个动态规划问题：
markdown
初始化 next[0]=-1 或者 0。
for i=1 to P.length：
while t != -1 and Pattern[next[t+1]] ≠ Pattern[i]:
t = next[t]
if Pattern[next[t + 1]] == Pattern[i]:
next[i]= next[t]+1;
else:
next[i]=t;
这里变量`t`代表上一次有效转移的结果值，通过不断地回溯并检查能否形成更长的有效前后缀来更新当前状态下的_next[i_]。
**Next数组的应用—— KMP 算法**
Next数组最经典也是最重要的应用场景是在 Knuth–Morris– Pratt(KMP) 字符串搜索算法里。传统的暴力子串查找每次发生失配都需要将目标串退回一位重新进行比对，而利用了预处理出的Next数组之后，即使遇到失配也能直接确定下一个可能匹配上的起点，无需像朴素解法那样重复扫描已知的部分，从而极大地提升了效率。
总结来说，Next数组是一种巧妙地利用已有信息避免无谓重试的技术手段，并已在实际工程、理论分析以及各类在线/offline竞赛中有广泛深入的应用，充分体现了数据结构优化解决复杂问题的魅力所在。