一、 串的存储结构：定长 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 就是为了跳过这些重复比较。
