字符串模式匹配与 KMP 做题实战全解

核心心法(刻在脑子里)

  1. next 数组极简递推口诀:前两位固定写 0, 1。求后位看前一位:字符相同则“前位 next ”;字符不同则“顺着 next 链一路回退比对”,退到 0 仍不同则直接填 !
  2. nextval 抄作业法则:第 1 位固定写 0。从第 2 位起本位与替身字符比对:相同借用别人的(抄替身的 ),不同用自己的(保留原 )!
  3. KMP 匹配做题灵魂铁律:主串指针 焊死绝不后退!模式串指针直接跳 (或 )!
  4. 计算比较次数草稿纸法则:两两字符碰面,不管匹配还是失配,计数器立刻 !失配后 原地不动,模式串查表滑动对齐,继续比对下一行!

🛠️ 第一部分:按视频思路手算 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 位前面的子串)为例

子串长度 , 最大从 开始往下试:

  1. 试 :前 4 位 [a b a a] b("abaa") vs 后 4 位 a [b a a b]("baab") ❌ 不同;
  2. 试 :前 3 位 [a b a] a b("aba") vs 后 3 位 a b [a a b]("aab") ❌ 不同;
  3. 试 :前 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. 取第 位的字符 ,与当前 所指向的字符 进行比对;
    2. 若相同(比对成功):直接在当前成功的 上 ,即 ====;
    3. 若不同(比对失败):顺着链条回退,更新 ====:
      • 若新的 ,拿 与新的 继续比对;
      • 若退到 仍无匹配,直接填 ====。

考场高频卡壳点:中途回退后才比对成功,到底用谁 ?

很多同学在“第一次比对失败、第二次(或第 次)才比对成功”时,会纠结到底是用 、前一位下面的数 ,还是当前位置 ?

  • 唯一铁律:==永远是“当前终于比对成功的那个替身序号 ”加 ()!==
  • 只有第 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',回退 ,触底 。
  • 第 5 位:
    • 看第 4 位 'a',初始 ():'a' == 'a'(一次成功)。
  • 第 6 位(⭐ 类型一:回退 1 次后在中间比对成功):
    • 看第 5 位 'a',初始 ():'a' != 'b'(第 1 次失败);
    • 回退 ():'a' == 'a'(第 2 次比对成功!);
    • 用当前成功的 加 !
  • 第 7 位:
    • 看第 6 位 'b',初始 ():'b' == 'b'(一次成功)。
  • 第 8 位(⭐ 类型二:连续回退到 0):
    • 看第 7 位 'b',初始 ():'b' != 'c';
    • 回退 ():'b' != 'a';
    • 再回退 :已触底到 0 !
  • 第 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 次比对成功!);
    • 立刻刹车!用当前成功的 加 (绝不是 )!
  • 第 17 位:
    • 看第 16 位 'a',初始 ():'a' == 'a'(一次成功)。

3. 优化版 nextval 数组计算:“抄作业法则”

为什么要优化出 nextval?

如果模式串第 位的字符 与它滑过去要比对的替身字符 长得一模一样: 既然 本身已经失配了,那替身字符去了也必定失配!何必多比一次呢? 所以当字符相同时,直接跳过替身,直接抄替身的 nextval!

秒求规则(记住两句话):

  1. 第 1 位固定写 0()。
  2. 从第 2 位开始,比对本位字符 与 指向的替身字符 :
    • 字符相同 借用别人的值:抄替身的 nextval,即 ;
    • 字符不同 用自己的值:保留自己的原 next,即 。

17 位模式串的 nextval 对照表:

序号 字符 原 替身位置与字符 是否相同?(本位 vs 替身)决策规则最终
1a0--固定第 1 位==0==
2b1'b' != 'a'(不同)用自己的原 next==1==
3c1'c' != 'a'(不同)用自己的原 next==1==
4a1'a' == 'a'(相同)借别人的 ==0==
5a2'a' != 'b'(不同)用自己的原 next==2==
6b2'b' == 'b'(相同)借别人的 ==1==
7b3'b' != 'c'(不同)用自己的原 next==3==
8c1'c' != 'a'(不同)用自己的原 next==1==
9a1'a' == 'a'(相同)借别人的 ==0==
10b2'b' == 'b'(相同)借别人的 ==1==
11c3'c' == 'c'(相同)借别人的 ==1==
12a4'a' == 'a'(相同)借别人的 ==0==
13a5'a' == 'a'(相同)借别人的 ==2==
14b6'b' == 'b'(相同)借别人的 ==1==
15c7'c' != 'b'(不同)用自己的原 next==7==
16a4'a' == 'a'(相同)借别人的 ==0==
17b5'b' != 'a'(不同)用自己的原 next==5==


🎯 第二部分:拿到 next 和 nextval 之后,考场上到底怎么做题?

破除迷茫:算出了数字,到底在题目里怎么用?

很多同学算出了 next = [0, 1, 1, 2...],但一看到题目让算比较次数或者失配指针位置就彻底懵了。 其实,KMP 在考场上只有 三大标准题型。学长带你把每一种题型的机械破题 SOP 彻底固化下来!

🔍 核心物理图像:双指针在字符串上到底怎么动?

设主串为 (指针为 ),模式串为 (指针为 ):

  1. 字符匹配成功():
    • 比较计数器:====;
    • 指针推进: 和 同时向前走一步()。
  2. 字符发生失配():
    • 比较计数器:==立刻 ==(失配这一次也是货真价实的比对,千万别漏加!);
    • 主串指针 焊死在原地,绝对不后退!
    • 模式串指针滑动:令 (或 );
    • 这在物理上相当于:把模式串向右滑动,让它的第 位正对着当前的 ,下一轮继续比对!
  3. 特别情况( 滑到了 0):
    • 如果模式串第 1 位就和 失配,,此时模式串已经退无可退;
    • 解决办法:主串往后走一位(),模式串重新归位为第 1 位(),继续新一轮比对。
  4. 大功告成(刹车标志):
    • 当模式串最后一位比对成功( 走完了模式串全长),匹配成功,立即停止计数!主串后面哪怕还有一千个字符,也绝不再比!

🏆 题型一:计算“单个字符间的比较次数”(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 位全部比对完毕,匹配成功!刹车终止!

命题人的两大陷阱

  1. 为什么有人会错选 A(9 次)?
    • 因为很多考生误以为“失配不算成功比对”,漏掉了第 6 次( 与 )那一次碰面!失配必须先比对才能知道失配,绝对要计入 1 次比较!
  2. 为什么选项 D 偏偏是 15 次?
    • 如果这道题用传统的 BF 朴素匹配算法(暴力匹配):
      • 第一趟(以 为起点):比对 6 次失配,主串回退到 ;
      • 第二趟(以 为起点):,比对 1 次失配,主串回退到 ;
      • 第三趟(以 为起点):比对 2 次()失配,主串回退到 ;
      • 第四趟(以 为起点):完全匹配成功,比对 6 次;
      • !选项 D 正是命题人给用错算法的考生挖的陷阱!

🏆 题型二:失配后指针走向问题(2015 年 408 统考第 8 题)

这类题考查对 KMP 指针跳跃机制和下标体系的敏锐度。

【2015 年 408 统考真题 第 8 题】
已知字符串 为 "abaabaabacacaabaabcc",模式串 为 "abaabc"。采用 KMP 算法进行匹配,第一次出现“失配”()时,,则下次开始匹配时, 和 的值分别是( )。
A.    B.    C.    D.

秒杀 SOP(10 秒出答案):

  1. 看主串指针 (秒杀核心):
    • KMP 算法的灵魂就是:主串指针绝不后退!
    • 失配时主串指针原地待命,因此下次开始匹配时, 必定保持原值 ====!
    • 一瞬间排除 A()和 D()!
  2. 看模式串指针 (查表与下标对齐):
    • 题干中写 ,模式串 "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:

  1. 搞懂什么是“右滑距离”:
    • 模式串在第 位与主串失配后,会滑动使第 位与主串当前字符对齐;
    • 向右滑动的字符格数公式:
  2. 第一步:手算模式串 的 数组:
    • ;
    • (前缀 "aa",长度 1);
    • (前缀 "aab",长度 0);
    • (前缀 "aaba",相等前后缀 "a",长为 1);
    • (前缀 "aabaa",相等前后缀 "aa",长为 2)。
      。
  3. 第二步:用“抄作业法则”秒求 :
    • :固定为 0;
    • :,替身 (相同) 抄 0;
    • :,替身 (不同) 抄原 2;
    • :,替身 (相同) 抄 0;
    • :,替身 (相同) 抄 0;
    • :,替身 (相同) 抄 2。
      。
  4. 第三步:列表计算每一位的右滑距离 :
    • 处失配: 格;
    • 处失配: 格;
    • 处失配: 格;
    • 处失配: 格;
    • 处失配: 格!(达到极值);
    • 处失配: 格。


⚔️ 第三部分:朴素匹配算法(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 个字符即失配,迅速滑向末尾)
最坏时间复杂度====(每次比到模式串尾部才失配)====
回溯代价极高,存在大量机械重复比对零回溯,利用自身对称性跨越无效比对

⚠️ 第四部分:命题人考场避坑指南(四绝)

考场四大致命失分雷区

  1. 失配那一次比较切勿漏算(最高频失分点!):
    • 只要主串字符与模式串字符碰面了,不论相等还是失配,计数器立刻 !
    • 记住了:先比对,才能发现失配;不能因为失配了就把这一步从历史上抹除!
  2. 失配时主串指针到底动不动?:
    • KMP 算法失配时,主串指针 原地不动!挪动的是模式串,是用模式串的第 位迎上去和当前的 继续比。
    • 选项中只要出现失配后 减小的选项,直接秒杀排除!
  3. 看清数组下标是 0 起始还是 1 起始:
    • 严蔚敏教材与大部分题目默认 1 起始();
    • 若真题如 2015 年第 8 题从 0 起始(),所有下标与数组数值全体减 1(),千万别死记模板导致结果偏移!
  4. 匹配成功的刹车时机:
    • 当模式串最后一位 比对成功后,模式匹配立即宣告成功并终止,主串中后续剩余的字符绝不再比!