核心内容摘要
根植沃土，繁茂枝繁：拔插拔插海外华人，连接世界的东方力量
串的存储结构定长 vs 堆串是由零个或多个字符组成的有限序列。
在 C 语言中我们主要关注两种实现定长顺序存储使用静态数组char str[MAXSIZE]。
缺点是长度固定容易发生截断。
堆分配存储重点使用malloc()动态分配空间。
typedef struct { char *ch; // 若是非空串则按串长分配存储区否则 ch 为 NULL int length; // 串长度 } HString;
模式匹配寻找子串的艺术所谓模式匹配就是在大串主串 S中找到小串模式串 T出现的位置。
BF 算法 (Brute-Force) —— 暴力美学原理逐个比对。
如果不匹配主串回溯到上一次起始位置的下一个模式串从头开始。
缺点大量回溯效率低下。
时间复杂度为 $。
KMP 算法 —— 拒绝无用功KMP 的核心在于主串指针不回溯只让模式串向右“滑动”到最合适的位置。
核心黑盒next数组next[j]的定义是当模式串中第个字符与主串失配时模式串应该退回到哪个位置重新比较。
手算next数组的保姆级步骤第1位next[1] 0固定规则。
第2位next[2] 1固定规则。
第 j 位看第位之前的字符串寻找“最长相等前后缀”。
例如串ababa当 $j4$ 时前面的串是aba。
前缀{a, ab}后缀{ba, a}。
最长相等前后缀是a长度为 1。
则next[4] 长度 1 2。
KMP 核心代码深度注释很多同学看不懂get_next函数关键在于理解它本质上是一个“模式串自己匹配自己”的过程。
void get_next(String T, int next[]) { i 1; j 0; next[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { // 如果 j0 说明要从头开始匹配 // 如果 ch[i] ch[j] 说明当前字符匹配成功前后缀长度加 1 i; j; next[i] j; } else { // 【深度注释】关键回溯点 // 如果不匹配j 回退到 next[j] 的位置 // 这种跳跃式回退利用了已有的匹配信息 j next[j]; } } }
深度复盘KMP 为什么快在 AI 领域或大规模数据检索中字符串匹配极度频繁。
空间换时间KMP 预先分析模式串的结构生成next数组避免了主串的重复扫描。
流式处理友好由于主串不回溯KMP 非常适合处理无法回头读取的数据流。
今日对比
总结特性BF 算法KMP 算法主串指针 $i$频繁回溯一直向前不回头模式串指针 $j$每次失配回到 1回到next[j]时间复杂度适用场景短串、简单匹配长串、模式串有大量重复片段时今日避坑指南索引起点严版教材中串通常从索引1开始ch[0]弃用或存长度。
如果你的代码从0开始next数组的值需要整体偏移。
优化版 nextval当模式串出现连续重复字符如aaaaab时普通的next会进行无意义的比较。
nextval就是为了跳过这些重复比较。