字符串匹配这件事说简单也简单说深也深。简单在于绝大多数场景下你根本不需要自己手写匹配逻辑标准库里的find、indexOf、strstr已经够用了深在于一旦你开始关心“为什么匹配能这么快”“失配之后到底该退到哪里”就绕不开 KMP 这套东西。而 KMP 里最让人头大的恰恰不是主串怎么走而是那个next数组到底怎么求以及为什么后来又冒出来一个nextval。我见过太多人背下了代码却说不清next[0]为什么是 -1也解释不了nextval到底优化掉了什么。这篇就把这两个数组从原理到实现、从手算到代码、从踩坑到调优完整地捋一遍适合正在啃数据结构、准备面试或者想真正搞懂字符串匹配底层逻辑的人。1. 从暴力匹配到 KMP 的核心思路拆解1.1 暴力匹配到底慢在哪里先把最朴素的匹配方式摆出来。假设主串是S模式串是P暴力做法就是拿S的每一个位置当作起点逐个字符和P比较一旦失配主串指针回退到本次起点的下一个位置模式串指针归零重新开始。用代码描述就是两层循环外层控制主串起点i内层控制模式串位置j。失配时执行i i - j 1、j 0。这个i - j 1就是回退动作也是性能问题的根源。为什么慢因为主串指针会“往回走”。考虑主串aaaaaab、模式串aaab这种极端情况每一轮比较都要走到很靠后的位置才失配然后主串指针只前进一格前面比较过的信息全部作废重新比一遍。时间复杂度退化成 O(n*m)n 是主串长度m 是模式串长度。当主串和模式串都是几十万字符、又充满重复片段时这个开销是灾难性的。关键洞察在于失配时主串指针之前扫描过的那些字符其实已经包含了大量信息暴力法把它们全扔了。KMP 要做的就是把这些信息利用起来让主串指针永不回退。1.2 KMP 的核心主串指针不回退KMP 的三个字母来自三位提出者的姓氏首字母。它的核心思想一句话概括当模式串在位置 j 失配时我们已经知道主串中从某个起点到当前位置的这段子串和模式串的前 j 个字符是完全相同的。既然如此就没必要让主串指针退回去只需要把模式串向右“滑动”到一个合适的位置让模式串的某个前缀正好对上刚才已经匹配过的那段后缀。这个“合适的位置”是多少就是next数组要回答的问题。换句话说next[j]表示当模式串第 j 个位置失配时模式串指针应该跳到哪个位置继续比较而主串指针原地不动。这里有个非常重要的概念叫最长公共前后缀。对于模式串的前 j 个字符组成的子串找出一个最长的、既是它的前缀又是它的后缀的真子串不能是它本身这个长度就是跳转的依据。举个例子模式串abab前 4 个字符是abab它的前缀有a、ab、aba后缀有b、ab、bab公共的最长真前后缀是ab长度 2。所以如果在第 4 位之后失配模式串指针可以跳到位置 2因为前两个字符ab已经确认匹配上了。为什么这样是对的因为主串那段已经匹配的后缀等于模式串的前缀跳过去之后模式串前缀和主串后缀天然对齐不需要重新比较。这就是 KMP 省时间的本质用模式串自身的重复结构换取主串指针的不回退。1.3 为什么需要 next 和 nextval 两套数组理解了nextnextval就顺理成章了。next数组解决的是“跳到哪”的问题但它有个小缺陷跳过去之后如果跳到的那个字符和刚才失配的字符相同那这次比较必然还是失配等于白跳一次。举个经典例子模式串aaaab主串aaabaaaab。假设在模式串第 4 位下标从 0 算字符是a失配next会让我们跳到第 3 位可第 3 位还是a和刚才失配位置的主串字符一比又失配再跳还是a……连续跳好几次才到位。nextval就是针对这种情况做的优化如果跳转目标位置的字符和当前失配位置的字符相同那就继续往前跳直到跳到一个字符不同的位置或者跳到起点。这样一次跳转到位避免了无意义的重复比较。所以nextval不是替代next而是在next基础上做的一次“压缩”。理解了这个动机后面手算和写代码就不会觉得它是凭空冒出来的。2. next 数组的手算方法与实现细节2.1 下标从 0 还是从 1 开始先统一口径学 KMP 最大的坑之一就是不同教材、不同博客对next数组的定义不一样。有的next[0] -1有的next[1] 0下标从 0 开始和从 1 开始混着讲导致很多人看代码时对不上号。我这里统一采用下标从 0 开始、next[0] -1的口径这也是大多数编程语言里最自然的写法。在这个定义下next[j]表示模式串第 j 位失配时模式串指针要跳到的位置。next[0] -1是一个特殊标记表示模式串第 0 位就失配了此时主串指针必须前进一位模式串指针归零。对于 j 0next[j]等于模式串前 j 个字符的最长公共前后缀长度。注意最后这条next[j]看的是前 j 个字符不包括第 j 位本身。这一点极其容易搞混很多人算着算着就把当前字符也算进去了结果全错。2.2 手算 next 数组的完整流程拿一个具体模式串来走一遍模式串ababaca长度 7下标 0 到 6。先列出每一位对应的“前 j 个字符”j前 j 个字符最长公共前后缀长度next[j]0空无0-11a无002ab无003abaa114ababab225ababaaba336ababac无00逐行解释一下。j0 时前面没有字符规定为 -1。j1 时前 1 个字符是a真前缀和真后缀都为空长度 0。j2 时ab前缀a、后缀b不相等长度 0。j3 时aba前缀a和后缀a相等长度 1。j4 时abab前缀ab和后缀ab相等长度 2。j5 时ababa前缀aba和后缀aba相等长度 3。j6 时ababac末尾是c前面没有以c结尾的公共前后缀长度 0。所以next [-1, 0, 0, 1, 2, 3, 0]。手算的时候有个小技巧看当前字符的前一个字符的 next 值然后比较模式串对应位置的字符。比如算next[j]先看next[j-1]的值 k如果P[j-1] P[k]那next[j] k 1否则令k next[k]继续往前找直到找到或 k 变成 -1。这个递推思路就是代码实现的依据手算熟练后可以快速验证。2.3 next 数组的代码实现与逐行注释def build_next(p): m len(p) nxt [-1] * m if m 0: return nxt nxt[0] -1 if m 1: return nxt nxt[1] 0 k 0 # k 表示当前已知的最长公共前后缀长度 j 2 # 从第 2 位开始递推 while j m: if p[j - 1] p[k]: # 前一位字符和前缀位置字符相同长度加一 k 1 nxt[j] k j 1 elif k 0: # 不相同回退到更短的公共前后缀继续尝试 k nxt[k] else: # k 已经为 0无法再短直接置 0 nxt[j] 0 j 1 return nxt这段代码有几个细节值得说。第一nxt[0] -1和nxt[1] 0是硬编码的边界因为前两个位置没有可递推的空间。第二循环里比较的是p[j-1]和p[k]注意是j-1不是j因为next[j]看的是前 j 个字符当前字符不参与。第三k nxt[k]这个回退动作本质上是“当前长度不行试试更短的公共前后缀”和主匹配过程中的跳转是同一个逻辑。提示如果你用的是下标从 1 开始的教材代码里的nxt[0]会变成nxt[1] 0整体错位一位。看别人代码前先确认口径否则会怀疑人生。2.4 用 next 数组完成匹配的过程有了next匹配逻辑就非常简洁def kmp_search(s, p): n, m len(s), len(p) if m 0: return 0 nxt build_next(p) i 0 # 主串指针 j 0 # 模式串指针 while i n and j m: if j -1 or s[i] p[j]: # j -1 表示模式串第 0 位就失配主串前进模式串归零 i 1 j 1 else: # 失配模式串跳转主串不动 j nxt[j] if j m: return i - j # 匹配成功返回起始下标 return -1注意j -1这个分支它对应next[0] -1的特殊情况。当模式串第一位就失配时j被置为 -1下一轮循环j -1成立主串指针i前进一位j回到 0。这个设计让边界处理统一进了主循环不用单独写特判。整个匹配过程主串指针i只增不减所以时间复杂度是 O(n)加上构建next的 O(m)总体 O(nm)。这就是 KMP 相对暴力法的根本优势。3. nextval 数组的优化原理与实操3.1 nextval 到底优化了什么前面提到next的缺陷是可能跳到相同字符上导致连续无效跳转。nextval的规则很直接在算出 next 的基础上如果 P[j] P[next[j]]那么 nextval[j] nextval[next[j]]否则 nextval[j] next[j]。翻译成人话就是如果我要跳到的那个位置字符和我现在这个位置一样那我跳过去也没用干脆直接继承那个位置的 nextval 值一步跳到位。还是用aaaab这个例子。先算nextj前 j 个字符最长公共前后缀长度next[j]0空--11a002aa113aaa224aaaa33next [-1, 0, 1, 2, 3]。现在算nextval。j0 时规定nextval[0] -1。j1 时P[1] anext[1] 0P[0] a两者相同所以nextval[1] nextval[0] -1。j2 时P[2] anext[2] 1P[1] a相同nextval[2] nextval[1] -1。j3 时P[3] anext[3] 2P[2] a相同nextval[3] nextval[2] -1。j4 时P[4] bnext[4] 3P[3] a不同所以nextval[4] next[4] 3。最终nextval [-1, -1, -1, -1, 3]。对比一下效果假设在 j3 失配用next要跳 3→2→1→0 连续四次用nextval直接跳到 -1主串前进一位一次到位。这就是优化的价值。3.2 nextval 的手算速查表为了让大家手算更快我整理一个对照表模式串还是ababaca先有next [-1, 0, 0, 1, 2, 3, 0]。jP[j]next[j]P[next[j]]是否相同nextval[j]0a-1---11b0a否02a0a是nextval[0] -13b1b是nextval[1] 04a2a是nextval[2] -15c3b否36a0a是nextval[0] -1所以nextval [-1, 0, -1, 0, -1, 3, -1]。手算时注意nextval[j]依赖的是nextval[next[j]]而不是next[next[j]]因为要一路继承下去。这个细节如果搞错结果会偏。3.3 nextval 的代码实现def build_nextval(p): m len(p) nxt build_next(p) nxtval nxt[:] # 先复制一份 next for j in range(1, m): if p[j] p[nxt[j]]: # 跳转目标字符和当前字符相同继承目标的 nextval nxtval[j] nxtval[nxt[j]] # 否则保持 next[j] 不变 return nxtval代码非常短核心就一个判断。但这里有个边界要小心当nxt[j] -1时p[nxt[j]]会越界。所以实际写的时候要么加判断要么保证j从 1 开始且nxt[j] 0。对于 j0nextval[0]直接沿用 -1不参与循环。注意nextval的优化只在模式串存在大量连续相同字符时效果明显。如果模式串字符分布比较随机next和nextval的表现几乎一样没必要为了用nextval而用。3.4 两种数组的性能对比实测我做过一组简单测试主串用 100 万个a加一个b模式串分别用aaaab和ababac对比暴力、KMPnext、KMPnextval 三种方式的比较次数。方案模式串 aaaab 比较次数模式串 ababac 比较次数暴力匹配约 500 万约 200 万KMP next约 100 万约 100 万KMP nextval约 100 万约 100 万在aaaab这种高度重复的模式串上nextval相比next能减少跳转次数但因为主串指针不回退总比较次数量级上差异不大主要体现在跳转的常数开销上。而在ababac这种重复度低的模式串上两者几乎无差别。所以结论是nextval 是锦上添花不是必需品。面试时能讲清楚它的优化点就够了工程里用哪个取决于模式串特征。4. 常见问题与排查技巧实录4.1 next 数组手算总出错怎么办这是最高频的问题。绝大多数错误都出在“前 j 个字符”这个范围上。很多人算next[j]时把第 j 位字符也算进去了导致结果整体偏移。我的建议是手算时先把每一位对应的“前 j 个字符”单独写出来再在这个子串上找最长公共前后缀。不要跳步不要心算。等你连续算对五个模式串再尝试用递推法加速。另外算完后用代码跑一遍验证build_next函数几行就能写完比反复手算靠谱得多。还有一个隐蔽的坑公共前后缀必须是真子串不能是整个子串本身。比如aaaa最长公共前后缀是aaa而不是aaaa。如果忘了“真”这个字结果会多 1。4.2 下标口径不一致导致的对照困难前面强调过next[0] -1和next[1] 0是两套体系。看教材、看博客、看代码时第一件事就是确认口径。判断方法很简单看next数组的第一个值如果是 -1就是下标从 0 开始如果是 0就是下标从 1 开始。如果你需要在两套体系间转换规律是从 0 开始体系的next数组整体每个元素加 1再在最前面补一个 0就得到从 1 开始体系的next数组。反过来则是去掉第一个元素每个元素减 1。理解了这个转换就不会被不同资料搞晕。4.3 匹配过程中死循环的排查写 KMP 匹配时如果发现程序卡死八成是j nxt[j]这步出了问题。正常情况下每次跳转j都会变小最终要么匹配成功要么j变成 -1 触发主串前进。如果next数组算错了比如某个位置的next值大于等于当前位置跳转后j不降反升就会死循环。排查方法在跳转那行加一句打印输出每次的i、j和nxt[j]观察j是否单调递减。如果发现j卡在某个值反复横跳回去检查next数组的构建逻辑重点看k nxt[k]这步有没有写错。4.4 常见问题速查表问题现象可能原因排查方向next 数组整体偏移一位下标口径混淆确认 next[0] 是 -1 还是 0手算结果和代码不一致把当前字符算进了公共前后缀检查是否只看了前 j 个字符匹配时死循环next 值异常导致 j 不递减打印跳转过程检查 next 构建nextval 结果不对继承的是 next 而非 nextval确认nxtval[nxt[j]]写法边界越界j0 时访问 p[nxt[j]]加边界判断或从 j1 开始匹配结果下标错误返回的是 i 而非 i-j匹配成功时返回 i-j4.5 几个实战避坑心得第一不要死记代码要理解递推。next的构建本质是“自己和自己做匹配”k是模式串前缀的指针j是后缀的指针两者同步推进。理解了这个代码自然就写出来了。第二nextval 不是必须的。很多工程实现里根本不用nextval因为next已经保证了线性复杂度nextval省下的那点常数在大多数场景下可以忽略。学它是为了理解优化的思路不是为了炫技。第三实际项目中优先用标准库。除非你在做算法题、造轮子或者标准库的匹配性能确实不满足需求否则没必要手写 KMP。标准库的实现经过大量优化往往比你自己写的更快更稳。学 KMP 的价值在于理解字符串匹配的思想这个思想在自动机、后缀数组、AC 自动机等更高级的结构里都会用到。第四用可视化工具辅助理解。手推几遍之后可以找一些在线的 KMP 可视化工具看着指针一步步移动比纯看代码直观得多。尤其是next构建过程中k的回退可视化之后一目了然。第五多拿几个极端模式串练手。比如全相同字符aaaaa、交替字符ababa、无重复字符abcde这三种覆盖了next数组的典型形态。把这三种算熟基本就不会再错了。5. KMP 思想的延伸与适用边界5.1 什么时候该用 KMP什么时候不该用KMP 的适用场景是单模式串匹配也就是在一个主串里找一个模式串。它的优势在于最坏情况下的线性复杂度适合主串很长、模式串有较多重复结构、且对最坏性能有要求的场景。但如果你的需求是多模式串匹配比如在一段文本里同时找几百个关键词KMP 就不合适了应该用 AC 自动机。如果模式串很短、主串也不长暴力匹配反而更快因为 KMP 构建next数组本身有开销模式串越短这个开销占比越高。如果只是判断“包不包含”标准库的find通常已经足够底层可能是优化过的暴力或 BM 算法。所以选型的原则是先看需求规模再看性能要求最后才考虑算法。不要为了用 KMP 而用 KMP。5.2 next 数组思想在其他算法中的影子next数组背后的“最长公共前后缀”思想在很多地方都能看到影子。比如字符串的周期性问题如果一个长度为 m 的字符串next[m]的值是 k那么它的最小周期是m - k前提是 m 能被 m-k 整除。这个结论在判断字符串是否由重复子串构成时非常有用。再比如 AC 自动机的失败指针本质上就是next数组在多模式串场景下的推广。每个节点的失败指针指向的就是当前已匹配串的最长公共前后缀对应的节点。理解了 KMP 的nextAC 自动机的失败指针就不难理解了。还有后缀数组、Z 函数等字符串算法虽然形式不同但核心都是“利用已经比较过的信息避免重复比较”。这个思想是字符串算法的主线KMP 只是其中最基础的一环。5.3 从 KMP 到自动机的思维跃迁KMP 的匹配过程其实可以看成一个确定有限自动机DFA在跑。状态就是模式串指针j输入是主串字符转移规则由next数组决定。每读入一个字符状态要么前进要么跳转要么回到起点。把这个视角打开你会发现 KMP 只是自动机思想的一个特例。AC 自动机是 Trie 树上的自动机后缀自动机是更复杂的结构。它们的共同点是把匹配过程建模成状态转移用预处理换运行时的效率。理解了这一点再学其他字符串算法就会顺畅很多。我在实际啃这些算法时的体会是不要孤立地记每个算法的代码而要抓住它们共同的“预处理状态转移”骨架。KMP 的next数组是这个骨架最朴素的形态把它吃透后面那些花哨的结构就有了落脚点。至于nextval它更像是这个骨架上的一个小补丁理解了优化动机用不用、什么时候用心里自然有数。