别再死记硬背了！用‘最长前后缀’这个核心概念，5分钟搞定KMP的next数组（附手算步骤）

从最长前后缀到next数组KMP算法的核心逻辑拆解每次遇到字符串匹配问题暴力解法总是最先浮现在脑海中——逐个字符比较不匹配就回退。这种简单粗暴的方法在大多数情况下确实有效直到你遇到一个超长文本串和模式串时间复杂度O(mn)的暴力匹配就显得力不从心了。这时KMP算法以其O(mn)的时间复杂度脱颖而出而理解它的关键就在于那个让人又爱又恨的next数组。1. 为什么需要next数组想象你正在用暴力方法匹配字符串ababc和abababc。当匹配到第五个字符时c≠a传统做法是将模式串整体后移一位重新开始。但仔细观察会发现模式串ababc的前四个字符abab已经匹配成功其中前两个ab和后两个ab完全相同。这意味着我们可以直接将模式串前移两位而不是一位因为前两位已经确定匹配。这就是next数组的精髓——它记录了模式串各部分的自相似信息告诉我们当匹配失败时模式串可以跳多远而不丢失已经匹配的信息。这种跳跃式的移动方式正是KMP算法高效的核心所在。提示next数组的值与模式串本身有关与被匹配的文本串无关这使得预处理阶段可以独立完成。2. 最长相等前后缀next数组的灵魂要理解next数组必须先掌握最长相等前后缀这一核心概念。给定一个字符串它的前缀是指从首字符开始的不包含末字符的子串后缀是指以末字符结束的不包含首字符的子串。以字符串ababa为例长度为1的子串a无前后缀定义上前后缀不能等于字符串本身ab前缀[a]后缀[b]无相等前后缀aba前缀[a,ab]后缀[a,ba]最长相等前后缀是a长度为1abab前缀[a,ab,aba]后缀[b,ab,bab]最长相等前后缀是ab长度为2ababa前缀[a,ab,aba,abab]后缀[a,ba,aba,baba]最长相等前后缀是aba长度为3next数组的定义就是对于模式串P的位置jnext[j]等于P[1..j-1]这个子串的最长相等前后缀长度加1假设字符串从1开始索引。3. 手算next数组的五步法则让我们以模式串ababaaababaa为例演示如何一步步计算next数组。记住这个五步流程初始化next[1] 0第一个字符没有前后缀截取子串对于每个j1考虑P[1..j-1]这个子串找出最长相等前后缀比较该子串的所有可能前后缀记录最大长度找到最长的那个相等前后缀的长度k赋值next[j] k 1具体计算过程jP[1..j]最长相等前后缀next[j]计算next[j]值1a无002ab无0113abaa (长度1)1124ababab (长度2)2135ababaaba (长度3)3146ababaaa (长度1)1127ababaaaa (长度1)1128ababaaabab (长度2)2139ababaaabaaba (长度3)31410ababaaabababab (长度4)41511ababaaababaababa (长度5)516最终得到的next数组为[0,1,2,3,4,2,2,3,4,5,6]4. 从next到nextval的优化之路标准的next数组在某些情况下仍有优化空间。考虑模式串aaaab和文本串aaabaaaab的匹配过程前三个字符匹配成功第四个字符不匹配a≠b根据next[4]3比较P[3]和当前文本字符P[3]还是a必然再次不匹配这种不必要的比较可以通过nextval数组避免nextval数组的计算基于next数组规则如下def compute_nextval(P, next): nextval [0] * len(P) nextval[0] -1 # 假设索引从0开始 for j in range(1, len(P)): if P[j] P[next[j]]: nextval[j] nextval[next[j]] else: nextval[j] next[j] return nextval以之前的ababaaababaa为例其nextval计算过程nextval[1] 0j2: P[2]b ≠ P[next[2]]P[1]a → nextval[2]next[2]1j3: P[3]a P[next[3]]P[2]b → nextval[3]nextval[next[3]]nextval[2]1j4: P[4]b P[next[4]]P[3]a → nextval[4]nextval[next[4]]nextval[3]1j5: P[5]a P[next[5]]P[4]b → nextval[5]nextval[next[5]]nextval[4]1j6: P[6]a ≠ P[next[6]]P[2]b → nextval[6]next[6]2j7: P[7]a P[next[7]]P[2]b → nextval[7]nextval[next[7]]nextval[2]1j8: P[8]a ≠ P[next[8]]P[3]a → nextval[8]nextval[next[8]]nextval[3]1j9: P[9]b P[next[9]]P[4]b → nextval[9]nextval[next[9]]nextval[4]1 10.j10: P[10]a P[next[10]]P[5]a → nextval[10]nextval[next[10]]nextval[5]1 11.j11: P[11]b P[next[11]]P[6]a → nextval[11]next[6]2最终nextval数组为[0,1,1,1,1,2,1,1,1,1,2]5. 常见陷阱与实战技巧在计算和应用next数组时有几个容易踩坑的地方索引从0还是1开始大多数编程语言中字符串索引从0开始但很多教材从1开始从0开始时next[0]通常设为-1作为特殊标记计算原理相同只是最终结果可能需要±1调整边界条件处理空字符串的next数组应返回空或特定标记单字符字符串的next数组值为[0]或[-1]取决于索引性能优化技巧在计算next数组时可以利用已知信息跳过部分比较对于长模式串可以预处理字符分布特征加速匹配实际面试中面试官可能会要求手算给定模式串的next数组解释KMP相比暴力匹配的优势分析特定情况下next数组的应用实现KMP算法的伪代码或实际代码记住这个计算next数组的通用模板def compute_next(P): next [0] * len(P) next[0] -1 i, j 0, -1 while i len(P) - 1: if j -1 or P[i] P[j]: i 1 j 1 next[i] j else: j next[j] return next理解KMP算法的关键在于将抽象的最长前后缀概念具象化为可操作的next数组计算步骤。通过模式串自身的结构信息来指导匹配过程这正是KMP算法巧妙之处。