字符串模式匹配与 KMP 做题实战全解
核心心法(刻在脑子里)
- next 数组极简递推口诀:前两位固定写
0, 1。求后位看前一位:字符相同则“前位 next ”;字符不同则“顺着 next 链一路回退比对”,退到 0 仍不同则直接填 !- nextval 抄作业法则:第 1 位固定写
0。从第 2 位起本位与替身字符比对:相同借用别人的(抄替身的 ),不同用自己的(保留原 )!- KMP 匹配做题灵魂铁律:主串指针 焊死绝不后退!模式串指针直接跳 (或 )!
- 计算比较次数草稿纸法则:两两字符碰面,不管匹配还是失配,计数器立刻 !失配后 原地不动,模式串查表滑动对齐,继续比对下一行!
🛠️ 第一部分:按视频思路手算 next 与 nextval(建立肌肉记忆)
核心认知:next 数组到底跟谁有关?
next 数组仅与模式串本身有关,与主串毫无关系!不管主串有一万个字符还是一亿个字符,拿到题第一步,只需把模式串单独拎出来排队求 next。
1. next 数组的两种手算方法
方法一:从前往后逐步观察法(定义法 · 适合前 3~5 位)
- 前两位固定死记:第 1 位必为 0,第 2 位必为 1(即 )。
- 从第 3 位开始的核心铁律:遮住当前字符,只看它前面的所有字符构成的子串(设子串长度为 ):
- 从头截取前 位,从尾截取后 位,从大到小看它们是否完全相同!
- 因为真前后缀不能包含子串自身,所以 最大从 ==== 开始往下尝试;
- 若找到相同的长度 :则 ====;
- 若尝试到 仍不存在任何相同的前后缀():则 ====。
考场极度致命误区:后缀绝对不能倒着读!不是回文串!
很多同学在这里脑子一热,误以为“后缀”是从尾巴往回倒着读(把
"ab"反着读成"ba",然后纳闷为什么对不上),这是绝对错误的!
- 铁律:不管是前缀还是后缀,全部严格按照从左向右的正常顺序读!
- 以子串
"abaab"(长度 5)为例:
- 前 2 位:第 1、2 位从左往右读是 ==
"ab"==;- 后 2 位:第 4、5 位从左往右读依然是 ==
"ab"==,绝不是"ba"!- 两头都是
"ab",完全相同,长度 !
🎬 慢动作全拆解示范:以 "abaab"(第 6 位前面的子串)为例
子串长度 , 最大从 开始往下试:
- 试 :前 4 位
[a b a a] b("abaa") vs 后 4 位a [b a a b]("baab") ❌ 不同; - 试 :前 3 位
[a b a] a b("aba") vs 后 3 位a b [a a b]("aab") ❌ 不同; - 试 :前 2 位
[a b] a a b("ab") vs 后 2 位a b a [a b]("ab") ✅ 完全相同!- 找到最长相等长度 ;
- 结论:!
方法二:利用已知值极速递推法(回溯法 · 第 4 位起考场提速)
考场实战黄金分工
- 第 1、2 位:直接固定写
0, 1;- 第 3 位:用方法一一眼秒杀(只看前 2 位字符:相同填
2,不同填1);- 第 4 位及以后:全用方法二极速递推,又快又稳!
- 核心逻辑:已经求出了前 位的 next,要求第 位的 next 值,设一个临时替身指针 ,初始令 :
- 取第 位的字符 ,与当前 所指向的字符 进行比对;
- 若相同(比对成功):直接在当前成功的 上 ,即 ====;
- 若不同(比对失败):顺着链条回退,更新 ====:
- 若新的 ,拿 与新的 继续比对;
- 若退到 仍无匹配,直接填 ====。
考场高频卡壳点:中途回退后才比对成功,到底用谁 ?
很多同学在“第一次比对失败、第二次(或第 次)才比对成功”时,会纠结到底是用 、前一位下面的数 ,还是当前位置 ?
- 唯一铁律:==永远是“当前终于比对成功的那个替身序号 ”加 ()!==
- 只有第 1 次就成功时, 恰好等于 (前一位下面的数),才会表现为 ;一旦第 1 次失败并回退了, 就已经作废了,必须用新跳到的那个 来 !
- 极简示范(求
"abaa"后第 5 位的 next):已知前 4 位为a(0), b(1), a(1), a(2),求 :
- 看第 4 位
'a',初始 (前一位下面的数):- 第 1 次比对: vs ❌ 不同!回退 ;
- 第 2 次比对: vs ✅ 成功!此时成功的指针是 ;
- 填值:(绝不是 ,更不是 )!
flowchart TD Start["求 next[k+1](已知前 k 位 next,k ≥ 3)"] --> Init["初始化替身指针:p = next[k]"] Init --> Compare{"比对 S[k] == S[p] ?"} Compare -- "✅ 相同(匹配成功)" --> Success["填值:next[k+1] = p + 1"] Compare -- "❌ 不同(失配)" --> Fallback["顺链回退:p = next[p]"] Fallback --> CheckP{"p > 0 ?"} CheckP -- "是(p > 0),继续比对" --> Compare CheckP -- "否(p == 0),已触底" --> Zero["填值:next[k+1] = 1"]
2. 经典例题实战:17 位超长模式串全推演(覆盖一次成功 / 中途回退成功 / 回退到 0)
模式串为:a b c a a b b c a b c a a b c a b(共 17 位)。
序号 j: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
模式串: a b c a a b b c a b c a a b c a b
next: 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 4 5
逐位手算推演全记录:
- 第 1、2 位:前两位固定写入:。
- 第 3 位(用方法一秒杀):看前 2 位
"ab",'a' != 'b',无相等前后缀 。 - 第 4 位(开始用方法二极速递推):
- 看第 3 位
'c',初始 ():'c' != 'a',回退 ,触底 。
- 看第 3 位
- 第 5 位:
- 看第 4 位
'a',初始 ():'a' == 'a'(一次成功)。
- 看第 4 位
- 第 6 位(⭐ 类型一:回退 1 次后在中间比对成功):
- 看第 5 位
'a',初始 ():'a' != 'b'(第 1 次失败); - 回退 ():
'a' == 'a'(第 2 次比对成功!); - 用当前成功的 加 !
- 看第 5 位
- 第 7 位:
- 看第 6 位
'b',初始 ():'b' == 'b'(一次成功)。
- 看第 6 位
- 第 8 位(⭐ 类型二:连续回退到 0):
- 看第 7 位
'b',初始 ():'b' != 'c'; - 回退 ():
'b' != 'a'; - 再回退 :已触底到 0 !
- 看第 7 位
- 第 9 位:看第 8 位
'c',初始 ():不同;退到 。 - 第 10 位:看第 9 位
'a',('a' == 'a')。 - 第 11 位:看第 10 位
'b',('b' == 'b')。 - 第 12 位:看第 11 位
'c',('c' == 'c')。 - 第 13 位:看第 12 位
'a',('a' == 'a')。 - 第 14 位:看第 13 位
'a',('a' == 'a')。 - 第 15 位:看第 14 位
'b',('b' == 'b')。 - 第 16 位(⭐ 类型三:大跨度回退后在中间比对成功):
- 看第 15 位
'c',初始 ():'c' != 'b'(第 1 次失败); - 回退 ():
'c' == 'c'(第 2 次比对成功!); - 立刻刹车!用当前成功的 加 (绝不是 )!
- 看第 15 位
- 第 17 位:
- 看第 16 位
'a',初始 ():'a' == 'a'(一次成功)。
- 看第 16 位
3. 优化版 nextval 数组计算:“抄作业法则”
为什么要优化出 nextval?
如果模式串第 位的字符 与它滑过去要比对的替身字符 长得一模一样: 既然 本身已经失配了,那替身字符去了也必定失配!何必多比一次呢? 所以当字符相同时,直接跳过替身,直接抄替身的 nextval!
秒求规则(记住两句话):
- 第 1 位固定写 0()。
- 从第 2 位开始,比对本位字符 与 指向的替身字符 :
- 字符相同 借用别人的值:抄替身的 nextval,即 ;
- 字符不同 用自己的值:保留自己的原 next,即 。
17 位模式串的 nextval 对照表:
| 序号 | 字符 | 原 | 替身位置与字符 | 是否相同?(本位 vs 替身) | 决策规则 | 最终 |
|---|---|---|---|---|---|---|
| 1 | a | 0 | - | - | 固定第 1 位 | ==0== |
| 2 | b | 1 | 'b' != 'a'(不同) | 用自己的原 next | ==1== | |
| 3 | c | 1 | 'c' != 'a'(不同) | 用自己的原 next | ==1== | |
| 4 | a | 1 | 'a' == 'a'(相同) | 借别人的 | ==0== | |
| 5 | a | 2 | 'a' != 'b'(不同) | 用自己的原 next | ==2== | |
| 6 | b | 2 | 'b' == 'b'(相同) | 借别人的 | ==1== | |
| 7 | b | 3 | 'b' != 'c'(不同) | 用自己的原 next | ==3== | |
| 8 | c | 1 | 'c' != 'a'(不同) | 用自己的原 next | ==1== | |
| 9 | a | 1 | 'a' == 'a'(相同) | 借别人的 | ==0== | |
| 10 | b | 2 | 'b' == 'b'(相同) | 借别人的 | ==1== | |
| 11 | c | 3 | 'c' == 'c'(相同) | 借别人的 | ==1== | |
| 12 | a | 4 | 'a' == 'a'(相同) | 借别人的 | ==0== | |
| 13 | a | 5 | 'a' == 'a'(相同) | 借别人的 | ==2== | |
| 14 | b | 6 | 'b' == 'b'(相同) | 借别人的 | ==1== | |
| 15 | c | 7 | 'c' != 'b'(不同) | 用自己的原 next | ==7== | |
| 16 | a | 4 | 'a' == 'a'(相同) | 借别人的 | ==0== | |
| 17 | b | 5 | 'b' != 'a'(不同) | 用自己的原 next | ==5== |
🎯 第二部分:拿到 next 和 nextval 之后,考场上到底怎么做题?
破除迷茫:算出了数字,到底在题目里怎么用?
很多同学算出了
next = [0, 1, 1, 2...],但一看到题目让算比较次数或者失配指针位置就彻底懵了。 其实,KMP 在考场上只有 三大标准题型。学长带你把每一种题型的机械破题 SOP 彻底固化下来!
🔍 核心物理图像:双指针在字符串上到底怎么动?
设主串为 (指针为 ),模式串为 (指针为 ):
- 字符匹配成功():
- 比较计数器:====;
- 指针推进: 和 同时向前走一步()。
- 字符发生失配():
- 比较计数器:==立刻 ==(失配这一次也是货真价实的比对,千万别漏加!);
- 主串指针 焊死在原地,绝对不后退!
- 模式串指针滑动:令 (或 );
- 这在物理上相当于:把模式串向右滑动,让它的第 位正对着当前的 ,下一轮继续比对!
- 特别情况( 滑到了 0):
- 如果模式串第 1 位就和 失配,,此时模式串已经退无可退;
- 解决办法:主串往后走一位(),模式串重新归位为第 1 位(),继续新一轮比对。
- 大功告成(刹车标志):
- 当模式串最后一位比对成功( 走完了模式串全长),匹配成功,立即停止计数!主串后面哪怕还有一千个字符,也绝不再比!
🏆 题型一:计算“单个字符间的比较次数”(2019 年 408 统考第 9 题)
这是 408 中考得最细、最容易粗心失分的王牌题型!
【2019 年 408 统考真题 第 9 题】
设主串"abaabaabcabaabc",模式串"abaabc",采用 KMP 算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是( )。
A. 9 B. 10 C. 12 D. 15
极速破题三步法:
- 第一步:先在草稿纸边缘秒算模式串的 数组
- 模式串 ,长度为 6。
- 第 1、2 位:固定 ;
- 第 3 位(方法一秒杀):看前 2 位
"ab",'a' != 'b'; - 第 4 位(方法二递推):看第 3 位
'a'与 的'a':第 1 次就相同 ; - 第 5 位(⚠️ 中途回退后第二次比对成功):看第 4 位
'a',初始 :- 第 1 次比对: vs ❌ 不同!回退 ;
- 第 2 次比对: vs ✅ 成功!用当前成功的 加 (绝不是前一位下面的数 );
- 第 6 位:看第 5 位
'b'与 的'b':第 1 次就相同 ; - 得到:。
- 第二步:画出比对草稿纸流水账(每比一次记一行,碰面就 )
| 比对序号 | 主串位置及字符 | 模式串位置及字符 | 碰面比对结果 | 指针动作与下一次状态 |
|---|---|---|---|---|
| 第 1 次 | ✅ 匹配 | |||
| 第 2 次 | ✅ 匹配 | |||
| 第 3 次 | ✅ 匹配 | |||
| 第 4 次 | ✅ 匹配 | |||
| 第 5 次 | ✅ 匹配 | |||
| 第 6 次 | ❌ ==失配!== | 计 1 次比对! 不动, 查表: | ||
| 第 7 次 | ✅ 匹配 | 模式串滑动后重连成功! | ||
| 第 8 次 | ✅ 匹配 | |||
| 第 9 次 | ✅ 匹配 | |||
| 第 10 次 | ✅ 匹配 | 模式串 6 位全部比对完毕,匹配成功!刹车终止! |
命题人的两大陷阱
- 为什么有人会错选 A(9 次)?
- 因为很多考生误以为“失配不算成功比对”,漏掉了第 6 次( 与 )那一次碰面!失配必须先比对才能知道失配,绝对要计入 1 次比较!
- 为什么选项 D 偏偏是 15 次?
- 如果这道题用传统的 BF 朴素匹配算法(暴力匹配):
- 第一趟(以 为起点):比对 6 次失配,主串回退到 ;
- 第二趟(以 为起点):,比对 1 次失配,主串回退到 ;
- 第三趟(以 为起点):比对 2 次()失配,主串回退到 ;
- 第四趟(以 为起点):完全匹配成功,比对 6 次;
- !选项 D 正是命题人给用错算法的考生挖的陷阱!
🏆 题型二:失配后指针走向问题(2015 年 408 统考第 8 题)
这类题考查对 KMP 指针跳跃机制和下标体系的敏锐度。
【2015 年 408 统考真题 第 8 题】
已知字符串 为"abaabaabacacaabaabcc",模式串 为"abaabc"。采用 KMP 算法进行匹配,第一次出现“失配”()时,,则下次开始匹配时, 和 的值分别是( )。
A. B. C. D.
秒杀 SOP(10 秒出答案):
- 看主串指针 (秒杀核心):
- KMP 算法的灵魂就是:主串指针绝不后退!
- 失配时主串指针原地待命,因此下次开始匹配时, 必定保持原值 ====!
- 一瞬间排除 A()和 D()!
- 看模式串指针 (查表与下标对齐):
- 题干中写 ,模式串
"abaabc"的第 6 个字符是'c'(即下标 5 对应第 6 个字符),说明本题采用的是以 0 为起始下标的体系! - 如果是从 1 开始计数:第 6 位
'c'的 ; - 平移法则:题目从 0 开始计数,所有序号与数组值全体减 1,故 !
- 因此下一次模式串指针跳跃为 ====。
- 题干中写 ,模式串
🏆 题型三:模式串失配时的“最长右滑距离”(2024 年 408 统考第 6 题)
这是 2024 年统考最新考法,直击 nextval 优化的几何滑动意义!
【2024 年 408 统考真题 第 6 题】
KMP 算法使用修正后的 数组()进行模式匹配,模式串 ’ “aabaab”,主串中某个字符失配时, 右滑最长距离为( )。
A. 5 B. 4 C. 3 D. 2
秒杀 SOP:
- 搞懂什么是“右滑距离”:
- 模式串在第 位与主串失配后,会滑动使第 位与主串当前字符对齐;
- 向右滑动的字符格数公式:
- 第一步:手算模式串 的 数组:
- ;
- (前缀
"aa",长度 1); - (前缀
"aab",长度 0); - (前缀
"aaba",相等前后缀"a",长为 1); - (前缀
"aabaa",相等前后缀"aa",长为 2)。
。
- 第二步:用“抄作业法则”秒求 :
- :固定为 0;
- :,替身 (相同) 抄 0;
- :,替身 (不同) 抄原 2;
- :,替身 (相同) 抄 0;
- :,替身 (相同) 抄 0;
- :,替身 (相同) 抄 2。
。
- 第三步:列表计算每一位的右滑距离 :
- 处失配: 格;
- 处失配: 格;
- 处失配: 格;
- 处失配: 格;
- 处失配: 格!(达到极值);
- 处失配: 格。
⚔️ 第三部分:朴素匹配算法(BF 算法)与 KMP 综合横向对比
408 考纲对“串”的模式匹配明确要求掌握:简单的模式匹配算法与 KMP 算法。
flowchart LR A["串的模式匹配"] --> B["BF 算法 (简单模式匹配)"] A --> C["KMP 算法"] B --> B1["失配时主串频繁后退:<br/>i = i - j + 2, j = 1<br/>时间复杂度: 最坏 O(n×m)"] C --> C1["主串指针焊死不回头:<br/>i 不动, j = next[j]<br/>时间复杂度: 稳定 O(n + m)"]
1. BF 算法指针回退公式(408 填空/选择常考)
若在主串第 位、模式串第 位失配:
- 主串指针回退到本次匹配起点的下一个位置:
- 模式串指针彻底归位:
2. BF vs KMP 核心指标对比表
| 对比维度 | BF 朴素模式匹配算法 | KMP 模式匹配算法 |
|---|---|---|
| 主串指针 | 频繁大幅度回退() | 绝对不回退,单调向右递增 |
| 模式串指针 | 彻底归位到开头() | 滑动跳跃到 或 |
| 最好时间复杂度 | (第 1 个字符即失配,迅速滑向末尾) | |
| 最坏时间复杂度 | ====(每次比到模式串尾部才失配) | ==== |
| 回溯代价 | 极高,存在大量机械重复比对 | 零回溯,利用自身对称性跨越无效比对 |
⚠️ 第四部分:命题人考场避坑指南(四绝)
考场四大致命失分雷区
- 失配那一次比较切勿漏算(最高频失分点!):
- 只要主串字符与模式串字符碰面了,不论相等还是失配,计数器立刻 !
- 记住了:先比对,才能发现失配;不能因为失配了就把这一步从历史上抹除!
- 失配时主串指针到底动不动?:
- KMP 算法失配时,主串指针 原地不动!挪动的是模式串,是用模式串的第 位迎上去和当前的 继续比。
- 选项中只要出现失配后 减小的选项,直接秒杀排除!
- 看清数组下标是 0 起始还是 1 起始:
- 严蔚敏教材与大部分题目默认 1 起始();
- 若真题如 2015 年第 8 题从 0 起始(),所有下标与数组数值全体减 1(),千万别死记模板导致结果偏移!
- 匹配成功的刹车时机:
- 当模式串最后一位 比对成功后,模式匹配立即宣告成功并终止,主串中后续剩余的字符绝不再比!