数据结构：（三）字符串——从暴力匹配到 KMP 的跨越
一、 串的存储结构：定长 vs 堆
串是由零个或多个字符组成的有限序列。在 C 语言中，我们主要关注两种实现：
定长顺序存储：使用静态数组
char str[MAXSIZE]。缺点是长度固定，容易发生截断。堆分配存储（重点）：使用
malloc()动态分配空间。typedef struct { char *ch; // 若是非空串，则按串长分配存储区，否则 ch 为 NULL int length; // 串长度 } HString;
二、 模式匹配：寻找子串的艺术
所谓模式匹配，就是在大串（主串 S）中找到小串（模式串 T）出现的位置。
1. BF 算法 (Brute-Force) —— 暴力美学
原理：逐个比对。如果不匹配，主串回溯到上一次起始位置的下一个，模式串从头开始。
缺点：大量回溯，效率低下。时间复杂度为 $
。
2. KMP 算法 —— 拒绝无用功
KMP 的核心在于：主串指针不回溯，只让模式串向右“滑动”到最合适的位置。
核心黑盒：next数组
next[j]的定义是：当模式串中第个字符与主串失配时，模式串应该退回到哪个位置重新比较。
手算next数组的保姆级步骤：
第1位：
next[1] = 0（固定规则）。第2位：
next[2] = 1（固定规则）。第 j 位：看第
位之前的字符串，寻找“最长相等前后缀”。
例如串
ababa：当 $j=4$ 时，前面的串是
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]) { // 如果 j==0 说明要从头开始匹配 // 如果 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就是为了跳过这些重复比较。