四、串

本章导览

共 3 个小节：串的定义和实现、朴素模式匹配算法、KMP 算法

本章重点

• 串 = 字符的线性表，重点是模式匹配
• 朴素匹配回溯主串 O(nm)；KMP 主串不回溯、靠 next 数组 O(n+m)

串的定义和实现

关键点

• 串 = 字符的有限序列，有顺序 / 链式存储
• 易错：空串（长度 0）≠ 空格串
• 操作：赋值、比较、求子串、连接、定位

朴素模式匹配算法

关键点

• 朴素匹配（BF）：逐位比，失配则主串指针回溯、模式串归零
• 最坏 O(nm)，有大量重复比较；简单但低效

KMP 算法

关键点

• KMP：失配时主串指针不回溯，模式串按 next 数组滑动，O(n+m)
• next[j] = 该位前子串的最长相等前后缀长；nextval 再优化
• 手算 next / nextval 必考

KMP算法核心

模式串的Next数组（手算练习）

关键点

• Next 数组：模式串第 j 个字符失配时，模式串指针跳到第 next[j] 位继续与主串比较（主串指针不回溯）
• next[j] = 第 j 位之前子串的「最长相等前后缀」长度，手算为高频考点

NextVal数组优化

关键点

• NextVal 是 next 数组的进一步优化：跳过「回退后字符仍相同」的无效比较
• 求法：从左到右，若 j 处字符与 next[j] 指向处相同，则 nextval[j] 取 nextval[next[j]]，否则取 next[j]