第4章 串
第4章 串¶
⚠️ 大纲仅要求掌握字符串模式匹配，重点是理解 KMP 算法的原理、next 数组和 nextval 数组的推导过程。 💡 教材建议：手算 next 数组时，可先求部分匹配值表再转换，也可直接用递推公式。
b_121_5【知识树】第4章骨架¶
- 串的定义：子串、主串、位置、空串 vs 空格串
- 串的基本操作与最小操作子集
- 串的存储：定长顺序、堆分配、块链
- 模式匹配
- 简单（暴力）匹配：O(nm)
- KMP：部分匹配值 PM → next 数组 → 匹配过程
- 优化：nextval 数组
b_121_0；PDF 第 121 页 · b_121_24.1 串的定义和实现¶
空串和空格串是一回事吗？¶
⚠️ 不是。 - 空串：长度 n = 0，用 ∅ 表示 - 空格串：由一个或多个空格组成的串，⚠️ 空格是一种特殊字符，其长度等于空格字符的个数
其他术语：子串（串中任意多个连续字符组成的子序列）、主串、位置（⚠️ 子串在主串中的位置以其第 1 个字符的位置标识）。 串相等的条件：⚠️ 长度相等且对应位置上的字符完全相同。
💡 教材例：A='China Beijing'、B='Beijing'、C='China'，长度分别 13、7、5；B 在 A 中的位置为 7，C 在 A 中的位置为 1。
b_121_7；PDF 第 121 页 · b_121_9串和线性表的区别在哪？¶
- 逻辑结构极为相似，区别仅在于串的数据对象被限定为字符集
- ⚠️ 基本操作差异显著：线性表以单个元素为单位（查找/插入/删除某个元素）；串一般以子串为单位（查找/插入/删除一个子串）
b_122_3串类型的最小操作子集是哪五个？¶
StrAssign（赋值）、StrCompare（比较）、StrLength（求长）、Concat（联接）、SubString（求子串）
⚠️ 它们无法通过其他串操作实现；⚠️ 其余串操作（除 ClearString 和 DestroyString 外）均可基于该最小子集实现。
💡 记忆法："赋、比、长、接、取"。
b_122_3；PDF 第 122 页 · b_122_4三种存储结构各是什么？¶
- 定长顺序存储：
char ch[MAXLEN]; int length;—— ⚠️ 超出 MAXLEN 的部分被舍弃，称为截断 - 串长两种表示：用整型变量显式记录；或末尾加不计入串长的结束标记 '\0'（⚠️ 此时串长是隐含值，要遍历计算）
- 堆分配存储：
char *ch; int length;—— ⚠️ 仍是地址连续的存储单元，但空间在运行时用 malloc() 动态申请，free() 释放 - 块链存储：⚠️ 每个链表结点可存放一个或多个字符，每个结点称为块；最后一块占不满时通常用 "#" 补齐
b_122_74.2 串的模式匹配¶
暴力匹配的复杂度怎么算出来的？¶
主串长 n、模式串长 m：⚠️ 最多需进行 n − m + 1 趟匹配，每趟最多比较 m 次 → 最坏 O(nm)。
失配时的回溯：i = i − j + 2; j = 1;（主串指针后退，模式串从头开始）。
💡 教材的极端例子：模式串 '0000001'、主串是大量 0 —— 每趟都要到模式串最后一个字符才发现不匹配，主串指针 i 回溯 39 次，总比较 40×7 = 280 次。
b_123_10；PDF 第 124 页 · b_124_4什么是前缀、后缀、部分匹配值？¶
- 前缀：⚠️ 除最后一个字符外，字符串的所有头部子串
- 后缀：⚠️ 除第一个字符外，字符串的所有尾部子串
- 部分匹配值：最长相等前后缀的长度
教材例 'ababa' 逐位推导： - 'a' → 前后缀均为空 → 0 - 'ab' → {a} ∩ {b} = ∅ → 0 - 'aba' → {a,ab} ∩ {a,ba} = {a} → 1 - 'abab' → {a,ab,aba} ∩ {b,ab,bab} = {ab} → 2 - 'ababa' → 交集 {a,aba} → 取最长 → 3
所以 'ababa' 的 PM 值为 00123。
b_125_0PM 表怎么指导右滑？（右滑公式）¶
教材例：主串 'ababcabcacbab'，模式串 'abcac'（PM = 00010） - 第一趟：第 3 位失配，已匹配 2 个 'ab'，最后匹配字符 b 的 PM = 0 → 2 − 0 = 2，右滑 2 位 - 第二趟：第 5 位失配，已匹配 4 个 'abca'，最后匹配字符 a 的 PM = 1 → 4 − 1 = 3，右滑 3 位 - 第三趟：全部匹配成功
⚠️ 两种情形都用同一个公式：PM = 0 时滑动最大（首字符直接对齐当前失配位置）；PM > 0 时滑到与相等后缀对齐的位置。 ⚠️ 特殊情况：模式串第一个字符就失配 → 已匹配字符数为 0 → 整体右移一位。
💡 主串指针始终不回溯，这使 KMP 的时间复杂度稳定为 O(n + m)。
b_125_12；PDF 第 125 页 · b_125_21next 数组和 PM 表是什么关系？（手算捷径）¶
next[j] 的含义：⚠️ 当模式串第 j 个字符失配时，下一轮应从模式串的第 next[j] 个位置继续与主串当前字符比较。
推导：
⚠️ 结论：next 数组 = PM 表右移一位，再整体加 1。 - ⚠️ 右移后空出的第一个位置补 0 —— 因为首字符失配时规定 next[1] = 0，表示主串和模式串同步右移一位 - ⚠️ PM 表最后一个元素右移后移出舍去 —— 因为它本是供下一个字符使用的，而最后一个字符没有下一个
例 'abcac'：PM = 0 0 0 1 0 → next = 0 1 1 1 2。
⚠️ 先声明约定，再算数组：
- 王道 1 基约定：next[1]=0，next[j]=PM[j-1]+1；失配时 j=next[j]，j==0 时才同时后移 i,j
- 0 基、-1 哨兵约定：next[0]=-1，j>0 时 next[j]=PM[j-1]；失配时同样 j=next[j]，j==-1 时同时后移 i,j
💡 例 aabaa：PM = 0 1 0 1 2；王道 1 基 next = 0 1 2 1 2；-1 哨兵 next = -1 0 1 0 1。
⚠️ 校订/边界：两套值相差 1，但只有在首项哨兵、下标范围和失配分支一起替换时才可转换；不能仅凭“选项从 0 开始”就机械加减。
💡 王道固定规则：next[1] = 0，next[2] = 1。
b_127_0next 数组的一般公式？¶
💡 直观含义：找模式串已匹配部分中"最长的相等前后缀"，让前缀滑过去顶替后缀的位置。 ⚠️ 不存在这样的相等前后缀时（视为 k = 1），主串第 i 个字符与模式串第 1 个字符重新比较。
b_127_19next 数组的递推怎么做？（两种情况）¶
设 next[j] = k，求 next[j+1]： - 若 pₖ = pⱼ → ⚠️ next[j+1] = next[j] + 1 = k + 1 - 若 pₖ ≠ pⱼ → ⚠️ 把求 next 视为一个模式匹配问题：令 k = next[k] 继续比较，若仍不匹配则继续 next[next[k]]…，直到找到某个 k′ 满足条件 → next[j+1] = k′ + 1；⚠️ 若始终找不到，则 next[j+1] = 1
教材算例（模式串 a b a a b c a b a，已知 next[1..6] = 0 1 1 2 2 3）： - 求 next[7]：next[6]=3，p₆ ≠ p₃ → 比较 p₆ 与 p₁（next[3]=1），p₆ ≠ p₁，next[1]=0 → next[7] = 1 - 求 next[8]：p₇ = p₁ → next[8] = next[7] + 1 = 2 - 求 next[9]：p₈ = p₂ → next[9] = 3
b_128_16KMP 匹配过程与暴力匹配差在哪一行？ ★1考¶
int Index_KMP(SString S, SString T, int next[]) {
int i = 1, j = 1;
while (i <= S.length && j <= T.length) {
if (j == 0 || S.ch[i] == T.ch[j]) { ++i; ++j; }
else j = next[j]; // ← 唯一的区别：主串指针 i 不动
}
if (j > T.length) return i - T.length;
else return 0;
}
⚠️ 失配时主串指针 i 保持不变，仅把模式串指针 j 回退到 next[j]；⚠️ 当 j = 0 时把 i 和 j 同时加 1（相当于模式串右滑一位，从主串第 i+1 位开始）。
💡 对齐图的理解法：失配前已匹配的后缀与模式串最长相等前缀已知相同，直接把该前缀对齐到后缀下方；i 留在失配字符，j 跳到新的待比位置。若已回退到哨兵，才让 i 前进。
⚠️ 一个反直觉的实务结论：尽管暴力匹配最坏 O(mn)、KMP 为 O(m+n)，但一般情况下暴力匹配的平均执行时间往往接近 O(m+n)，因此至今仍被采用；KMP 仅在存在大量"部分匹配"时才显著占优，其核心优点在于主串指针不回溯。
★ 考过 2015、2019
b_126_3nextval 数组解决了 next 的什么缺陷？ ★1考¶
问题：模式串 'aaaab'（next = 0 1 2 3 4）匹配主串 'aaabaaaab'。i=4、j=4 失配时，⚠️ next[4]=3 且 p₃ = p₄ = a，next[3]=2 且 p₂ = p₃，next[2]=1 且 p₁ = p₂ —— 这些回退位置上的字符都与 p₄ 相同，继续比较只会重复同样的失配。
⚠️ 根源：不应出现 pⱼ = p_{next[j]} —— 既然 pⱼ ≠ sᵢ，用与 pⱼ 相同的字符去匹配 sᵢ 必定仍失配。
修正办法：不断把 next[j] 替换为 next[next[j]]，直到 pⱼ ≠ p_k 或 k = 0，得到 nextval 数组。 教材例：'aaaab' 的 next = 0 1 2 3 4，nextval = 0 0 0 0 4。
代码关键两行：
⚠️ 匹配算法本身不变，只是把 next 换成 nextval。
💡 手算第二法：“有效前后缀”（先声明采用 0 基、-1 哨兵）： - 先按 next 找出失配位置前的最长相等前后缀 - 若该前缀之后的字符仍与当前失配字符相同，跳去仍会立即失配，因此继续改用更短的相等前后缀 - 直到“后继字符不同”或回到 -1，这个候选才是 nextval
例 aabaaba：next = -1 0 1 0 1 2 3，筛掉“跳过去还会撞上同一字符”的候选后，nextval = -1 -1 1 -1 -1 1 -1。
⚠️ 校订/边界：这是 nextval 递推的手算视角，不是另一种匹配算法；换回王道 1 基约定时，哨兵和数值也要整体换算。
★ 考过 2024
b_129_3【原书试题精选与答案方法】第4章¶
模式匹配的五个基础判断，怎样一次分清？¶
对应原书单选 01～05，答案依次为 C、B、C/D、D、B。
- “求模式串在主串中首次出现的位置”叫模式匹配，不是“求子串”。
- KMP 的标志不是“模式串不回退”，而是 ⚠️ 主串指针 \(i\) 不回溯；失配时保留 \(i\)，令 \(j=next[j]\)。
- 简单匹配的理论最坏复杂度是 \(O(mn)\)；KMP 是 \(O(m+n)\)。原书同时提醒：暴力法在一般数据上的实际表现可能接近 \(O(m+n)\)，但考试问复杂度时仍按最坏口径答 \(O(mn)\)。
💡 做判断题时抓住边界：若 \(j\) 回退到仍可比较的模式位置，主串指针 \(i\) 不动，当前字符继续参与比较；若已退到王道 1 基的 \(j=0\)（或 0 基的 \(j=-1\) 哨兵），下一步才让 \(i,j\) 同时前进。
b_131_6；PDF 第 131 页 · b_131_7；PDF 第 131 页 · b_131_8；PDF 第 131 页 · b_131_9；PDF 第 131 页 · b_131_10；PDF 第 131 页 · b_131_11；PDF 第 131 页 · b_131_12；PDF 第 131 页 · b_131_13原书单选 06 的 next 数组，怎样用 PM 表稳妥手算？¶
对模式串 ababaaababaa：
- 逐个前缀求“最长相等真前缀与真后缀长度”，得到 PM 表；
- 把 PM 表整体右移一位，低位补
-1，得到 0 下标口径的 next； - 本题选项采用 1 下标且 \(next[1]=0\) 的口径，因此再整体加 1。
最终选 C：
⚠️ next 表最常见的失分点不是前后缀，而是题目到底从 0 还是从 1 编号。算表前先写清口径。
b_131_14；PDF 第 131 页 · b_131_15；PDF 第 131 页 · b_131_16；PDF 第 131 页 · b_131_17；PDF 第 131 页 · b_131_18；PDF 第 131 页 · b_131_19原书单选 07～09，比较次数和 nextval 滑动距离怎么算？¶
答案：07 选 B（9 次）；08 选 C（7 次）；09 选 B（右滑 2 位）。
- 比较次数题：不要只数“对齐轮数”，要把每一轮实际发生的字符比较相加。原书 07 为 \(3+1+1+4=9\)。
- nextval 优化题：相同字符造成的无效比较会被跳过，原书 08 从 9 次降为 \(3+4=7\) 次。
- 滑动距离题：先按题目下标口径求表，再用
原书 09 在第 6 个字符（0 下标 \(j=5\)）失配，\(nextval[5]=3\)，故右滑 \(5-3=2\) 位。
💡 熟练后也可直接对齐模拟，但必须保证“已匹配前缀能否与其后缀复用”的判断和 nextval 一致。
b_131_20；PDF 第 131 页 · b_131_21；PDF 第 131 页 · b_131_22；PDF 第 132 页 · b_132_0；PDF 第 132 页 · b_132_1；PDF 第 132 页 · b_132_2；PDF 第 132 页 · b_132_3；PDF 第 132 页 · b_132_4；PDF 第 132 页 · b_132_5；PDF 第 132 页 · b_132_6；PDF 第 132 页 · b_132_7；PDF 第 132 页 · b_132_8；PDF 第 132 页 · b_132_9；PDF 第 132 页 · b_132_10；PDF 第 132 页 · b_132_11；PDF 第 132 页 · b_132_12；PDF 第 132 页 · b_132_132015 统考：第一次失配后，为什么是 \(i=5,j=2\)？¶
答案 C。 题目给出第一次失配时 \(i=j=5\)，由此先判断它采用 0 下标。模式串 abaabc 的 next 为
失配后 KMP 的动作是：主串指针 \(i\) 保持 5 不动，模式指针退到 \(next[5]=2\)，所以新一轮从 \(i=5,j=2\) 开始。
⚠️ 看到选项中同时出现“\(i\) 是否加 1”和“\(j\) 退到哪里”，先用 KMP 的不变量排掉所有让 \(i\) 回退或擅自前进的选项。
b_132_14；PDF 第 132 页 · b_132_15；PDF 第 132 页 · b_132_16；PDF 第 133 页 · b_133_02019 统考：KMP 到匹配成功共比较多少次？¶
答案 B，共 10 次。 模式串 abaabc 的 0 下标 next 为 \((-1,0,0,1,1,2)\)。
- 第一轮连续比较 6 次，在主串、模式串的 5 号位失配；
- 保持主串当前位置不动，把模式指针退到 \(next[5]=2\)；
- 第二轮再比较 4 次即匹配成功。
所以总次数为 \(6+4=10\)。
💡 这类题最稳的表格只记三列：当前 \(i\)、当前 \(j\)、本次比较后怎样更新。不要把“主串移动了几格”误当成“字符比较了几次”。
b_133_1；PDF 第 133 页 · b_133_2；PDF 第 133 页 · b_133_3；PDF 第 133 页 · b_133_42024 统考：修正 next 数组下，最长能右滑多少位？¶
答案 A，最长右滑 5 位。 对模式串 aabaab 求 0 下标 nextval，并逐位计算
各位置的滑动距离中，\(j=4\) 时 \(nextval[4]=-1\)，因此 \(d_4=4-(-1)=5\)，达到最大值。
⚠️ 题目问“某个字符失配时的最长距离”，必须逐位置比较 \(j-nextval[j]\)；不能只看 nextval 的最小值，也不能把模式串长度直接当答案。
b_133_5；PDF 第 133 页 · b_133_6；PDF 第 133 页 · b_133_7综合应用题 01：next 定义中的 0、max 与“其他”分别为什么？¶
原书的三个问法，实际是在解释 next 的边界、最优跳转与兜底：
- \(j=1\) 时取 \(next[1]=0\)：模式串首字符已经没有更短前缀可复用；若它失配，就让模式串右滑一位，并让主串转向下一个字符重新与模式首字符比较。
- 取 \(\max\{k\}\)：满足前缀等于后缀的 \(k\) 可能不止一个。右滑距离是 \(j-k\)，取最大的 \(k\) 就是取最小且不漏解的右滑距离；\(k\) 最大为 \(j-1\)。
- “其他”取 1：不存在可复用的非空相等前后缀，只能让模式首字符与主串当前字符再比较。
💡 本质：优先保留尽可能长的已匹配信息；完全无信息可保留时才退回模式首字符。
b_133_9；PDF 第 133 页 · b_133_10；PDF 第 133 页 · b_133_11；PDF 第 133 页 · b_133_12综合应用题 02（1）：aabaac 的 next 数组怎样递推出来？¶
采用原书 1 下标口径，先置 \(next[1]=0,next[2]=1\)。之后每求 \(next[j]\)：
- 令 \(k=next[j-1]\)；
- 若 \(P[j-1]=P[k]\)，则 \(next[j]=k+1\)；
- 若不等，就反复令 \(k=next[k]\)；退到 \(k=0\) 仍不等时，令 \(next[j]=1\)。
对 aabaac 逐位得到
⚠️ 在 \(j=4\) 时要经历 \(k=2\to1\to0\) 的连续回退；这一步正是“递推算法”区别于凭感觉看前后缀的关键。
b_133_13；PDF 第 133 页 · b_133_14；PDF 第 133 页 · b_133_15；PDF 第 133 页 · b_133_16；PDF 第 133 页 · b_133_17；PDF 第 134 页 · b_134_0；PDF 第 134 页 · b_134_2；PDF 第 134 页 · b_134_4；PDF 第 134 页 · b_134_6；PDF 第 134 页 · b_134_9；PDF 第 134 页 · b_134_10综合应用题 02（2）：aabaabaabaac 匹配 aabaac 为什么三趟成功？¶
沿用 \(next=(0,1,2,1,2,3)\)：
- 第一趟：前 5 个字符匹配，在 \(i=6,j=6\) 失配；令 \(j=next[6]=3\)，\(i\) 不动。
- 第二趟：从主串第 6 位与模式第 3 位继续，走到 \(i=9,j=6\) 再失配；仍令 \(j=3\)。
- 第三趟：从该位置继续，最终完整匹配成功，匹配起点是主串第 7 位。
💡 画对齐图时只做两件事：失配处的主串字符固定；把模式串第 \(next[j]\) 位移到它下面。 这样不会误把 KMP 画成暴力回溯。
b_134_11；PDF 第 134 页 · b_134_12；PDF 第 134 页 · b_134_13；PDF 第 134 页 · b_134_14；PDF 第 134 页 · b_134_15；PDF 第 134 页 · b_134_16；PDF 第 134 页 · b_134_17【原书归纳总结与思维拓展】第4章¶
KMP 为什么能把最坏复杂度从 \(O(mn)\) 降到 \(O(m+n)\)？¶
暴力匹配低效的根源是：失配后让主串回溯，导致已确认相等的字符被反复比较。KMP 先分析模式串自身，为每个失配位置预计算最佳跳转：
- 已匹配部分的后缀若等于模式串前缀，就把二者直接对齐；
- 对齐部分无需重比，主串指针不回溯；
- next 保存普通跳转，nextval 再消除“跳过去仍比较同一字符”的重复。
因此扫描主串和构造/使用模式信息都只需线性推进，整体按王道口径记为 \(O(m+n)\)。
b_135_0；PDF 第 135 页 · b_135_1怎样把 KMP 改成“统计主串中完整匹配次数”？¶
核心改动不是找到一次就返回，而是：
- 每当模式串全部匹配，计数器加 1；
- 为了不漏掉可重叠匹配，模式指针退回到能保留最长相等前后缀的位置；
- 主串继续向后扫描，直到结束。
⚠️ 若完整匹配后直接把模式指针清零，虽可能仍得到不重叠匹配，却会漏掉如 aaaa 中模式 aa 的重叠出现。统考通常不要求写完整 KMP 算法，但这道思维拓展能检验你是否真正理解“复用已匹配前后缀”。
b_135_2；PDF 第 135 页 · b_135_3【易混点】第4章成对概念对照¶
| 概念 A | 概念 B | 一句话切分 |
|---|---|---|
| 空串 | 空格串 | 长度 0 vs 长度 = 空格个数 |
| 串 | 线性表 | 操作以子串为单位 vs 以单个元素为单位 |
| 定长顺序存储 | 堆分配存储 | 编译期定长、会截断 vs 运行时 malloc |
| 前缀 | 后缀 | 除最后一个字符的所有头部子串 vs 除第一个字符的所有尾部子串 |
| PM 表 | next 数组 | next = PM 右移一位再加 1 |
| next | nextval | 可能出现 pⱼ = p_{next[j]} 的无效回退 vs 消除了这种回退 |
| 暴力匹配 | KMP | 主串指针要回溯、最坏 O(nm) vs 主串指针不回溯、稳定 O(n+m) |
| 王道 1 基约定 | 0 基、-1 哨兵约定 | next[1]=0，j==0 后移 vs next[0]=-1，j==-1 后移；必须整套换算 |
【必背数字】第4章¶
| 数字 | 含义 |
|---|---|
| n − m + 1 | 暴力匹配最多的趟数 |
| O(nm) / O(n+m) | 暴力匹配最坏 / KMP 时间复杂度 |
| next[1] = 0，next[2] = 1 | 固定规则 |
| next[j] = PM[j−1] + 1 | 手算捷径 |
| 右滑位数 = 已匹配字符数 − 对应 PM 值 | KMP 核心公式 |
| 'abcac' → PM 00010，next 01112 | 教材标准例 |
| 'aaaab' → next 01234，nextval 00004 | 优化对照例 |
| 'ababa' → PM 00123 | 部分匹配值推导例 |
| 五个 | 最小操作子集（赋值、比较、求长、联接、求子串） |
【口诀速记】第4章¶
| 维度 | 口诀 | 解释 |
|---|---|---|
| next 手算 | PM 右移一位再加一，首位补 0 | next[j] = PM[j−1] + 1 |
| 两个固定值 | next[1]=0，next[2]=1 | 不用推，直接写 |
| 编号约定 | 先看哨兵和失配分支，再做整体加减 | 1 基 j==0 与 0 基 j==-1 必须成套 |
| 右滑位数 | 已匹配字符数 − 对应 PM 值 | PM=0 时滑得最远 |
| nextval | 撞脸就继承 | pⱼ == p_{next[j]} 时，nextval[j] = nextval[next[j]] |
| KMP 本质 | 主串指针永不回溯 | 这是教材强调的核心机制与优势，比较次数题按此模拟 |
| 前缀后缀 | 前缀去尾，后缀去头 | 前缀是除最后一个字符的所有头部子串，后缀反之 |
b_121_3；PDF 第 121 页 · b_121_4【解题路线】第4章：KMP 题怎么下手¶
- ① 手算 next 的最快路径：先写部分匹配值表 PM → 整体右移一位 → 每项加 1 → 首位置 0
- ② 检查整套约定 → ⚠️ 看首项是
0还是-1，再看失配分支用j==0还是j==-1；只有整套一致时，王道 next 才能整体减 1 换成 -1 哨兵数组 - ③ 问 nextval：⚠️ 凡是 pⱼ == p_{next[j]} 的位置，nextval[j] 继承 nextval[next[j]]；否则 nextval[j] = next[j]
- ④ 问比较次数或指针变化：⚠️ 主串指针 i 永不回溯，失配时只把 j 退到 next[j]，逐趟模拟即可
- ⑤ 问右滑位数：已匹配字符数 − 对应的 PM 值
⚠️ 最容易错的两处：PM 表最后一位在转 next 时被舍去；next[1] = 0、next[2] = 1 是固定的，不用推。
⚠️ 零壹课件勘误（只作理解图，不照抄文字）：aabaa 的前缀第三项应为 aab，不是 aa；课件 p47 顶部所列数组实为 nextval；“整体 +1”只是 -1 哨兵数组向王道 1 基数组的整套约定转换，不是“选项从 0 开始”的通用规则。
b_121_5；PDF 第 121 页 · b_121_6