串：从定义到KMP，我踩过的那些坑
串，说白了就是字符串。在C语言里，我们天天跟它打交道。但真正把它当数据结构来研究，很多人是从这道题开始的。
我个人习惯把串看作「字符的线性表」。它跟数组很像，但操作上更讲究「模式匹配」。今天我们就从串的定义开始，一路聊到KMP算法。我会穿插一些项目里的真实教训，希望能帮你少走弯路。
串的定义与存储
串（String）是由零个或多个字符组成的有限序列。记作：S = "a1 a2 ... an"，其中 n 是串的长度。
- 空串：长度为0的串，写作
""。 - 空格串：只包含空格的串，长度不为0。
- 子串：串中任意连续字符组成的子序列。
- 主串：包含子串的串。
存储方式有两种：
| 存储方式 | 特点 | 我常用的场景 |
|---|---|---|
| 定长顺序存储 | 用固定长度数组，简单但浪费空间 | 嵌入式里，串长度已知时 |
| 堆分配存储 | 动态分配内存，灵活但需管理 | 通用场景，我90%的项目用这个 |
重要：C语言中串以 '\0' 结尾。这个结束符不计入串长度，但占用存储空间。很多bug就出在这里——分配内存时忘了给 '\0' 留位置。
我的习惯：定义串结构时，我会额外加一个 length 字段。这样就不用每次都调用 strlen() 了，效率高不少。
模式匹配算法（BF算法）
BF算法，全称Brute-Force，暴力匹配。思路很简单：从主串的第一个字符开始，逐个与模式串比较。如果匹配失败，主串指针回溯到下一个位置，模式串指针回到开头。
代码实现：
int BF(char *S, char *T) {
int i = 0, j = 0;
while (S[i] != '\0' && T[j] != '\0') {
if (S[i] == T[j]) {
i++; j++;
} else {
i = i - j + 1; // 主串回溯
j = 0; // 模式串重置
}
}
if (T[j] == '\0')
return i - j; // 匹配成功，返回位置
else
return -1; // 匹配失败
}
时间复杂度：最坏情况 O(n*m)，n为主串长度，m为模式串长度。
我曾经踩过的坑：有一次在嵌入式设备上做串口协议解析，用了BF算法。数据量一大，CPU占用率直接飙到80%。后来一查，模式串是"AT+OK"，主串里大量重复字符，BF算法疯狂回溯。嗯，从那以后，我对BF算法就多了一份警惕。
BF算法的优点是简单、易实现。缺点是效率低，尤其是当主串和模式串有大量重复字符时。
KMP算法原理
KMP算法（Knuth-Morris-Pratt）解决了BF算法的回溯问题。它的核心思想是：利用已经匹配的部分信息，让主串指针不回溯。
怎么做到的呢？关键在于一个「部分匹配表」（也叫next数组）。这个表记录了模式串中每个位置之前的子串的「最长相等前后缀长度」。
举个例子，模式串 "ABABAC"：
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 字符 | A | B | A | B | A | C |
| next | -1 | 0 | 0 | 1 | 2 | 3 |
next[5] = 3，表示 "ABABA" 的最长相等前后缀是 "ABA"，长度为3。
匹配时，如果模式串第 j 位匹配失败，主串 i 不动，模式串 j 跳到 next[j] 的位置继续比较。这样就避免了主串的回溯。
核心思想：KMP算法的时间复杂度是 O(n+m)，空间复杂度 O(m)。它用空间换时间，在模式串较长、重复字符多的情况下，优势非常明显。
KMP算法实现
先求next数组：
void getNext(char *T, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (T[i] != '\0') {
if (j == -1 || T[i] == T[j]) {
i++; j++;
next[i] = j;
} else {
j = next[j];
}
}
}
然后进行匹配：
int KMP(char *S, char *T) {
int i = 0, j = 0;
int next[strlen(T)];
getNext(T, next);
while (S[i] != '\0' && T[j] != '\0') {
if (j == -1 || S[i] == T[j]) {
i++; j++;
} else {
j = next[j]; // 主串不回溯
}
}
if (T[j] == '\0')
return i - j;
else
return -1;
}
我个人的建议：初学KMP时，别急着背代码。先拿笔在纸上画一遍next数组的推导过程。我当年就是画了十几遍才真正理解「前后缀」的含义。你想想看，如果连next数组怎么来的都不清楚，写出来的代码能对吗？
知识体系图
下面这张图展示了本章的核心逻辑：
总结
串的存储看似简单，但选错了方式，后面全是坑。BF算法适合短串或偶尔匹配的场景。KMP算法虽然实现复杂一点，但在重复匹配的场景下，性能提升是质的飞跃。
我个人建议：先把BF算法写熟，再啃KMP。别一上来就搞KMP，容易劝退。你想想看，连暴力匹配都写不利索，怎么可能理解KMP的精髓？
一句话记住KMP：主串不回头，模式串跳着走。next数组就是模式串的「导航地图」。