第 4 章 串
408 数据结构第 4 章 串复习讲义，涵盖核心概念、重点考点与典型题型。
Last updated on
一、先建立整章框架
这一章可以压缩成下面这条主线：
串是什么
↓
主串、子串、模式串
↓
在主串中找模式串
↓
朴素模式匹配
↓
发现大量重复比较
↓
KMP：主串指针不回退
↓
怎么知道模式串应该跳到哪里？
↓
前缀 / 后缀 / 部分匹配值 PM
↓
next 数组
↓
普通 next 仍可能重复比较
↓
nextval 优化所以如果问“第4章最核心的一句话是什么”，就是：
KMP 利用模式串自身的前缀—后缀性质，在失配时让主串指针不回退，只调整模式串指针。
二、4.1 串的定义和实现——理解即可
资料明确指出，4.1 并不是统考大纲的核心，主要是给后面的模式匹配打基础。
1. 什么是串
串就是由零个或多个字符组成的有限序列。
例如：
"abcde"
"408"
"hello world"
""都可以是串。
设串为：
其中字符数就是串长。
当字符数为 0 时，是空串。
这里特别容易混淆：
"" 空串，长度为 0
" " 空格串，长度为 1
" " 空格串，长度为 3因为空格本身也是字符。
2. 主串、子串、位置
例如：
S = "China Beijing"
T = "Beijing"那么 T 是 S 的一个子串。
资料采用从 1 开始的位置编号，因此 "Beijing" 在主串中的位置是 7。
这里以后和模式匹配直接联系起来：
主串 S：被搜索的大字符串
模式串 T：想寻找的小字符串模式匹配的目标就是：
找出模式串第一次完整出现在主串中的位置。
3. 串和线性表是什么关系
从逻辑结构上看，串很像线性表。
区别在于：
线性表：
一个元素可以是 int、结构体等各种数据。
串：
每一个元素必须是字符。更重要的区别是操作对象不同。
线性表经常讨论：
插入一个元素
删除一个元素
查找一个元素串经常讨论：
连接一个子串
删除一个子串
求一个子串
查找一个子串所以：
串可以看成一种特殊线性结构，但串算法经常以“一段字符”为操作单位。
三、串的基本操作
资料列出了赋值、复制、判空、比较、求长、求子串、连接、定位、清空、销毁等操作。
考试不需要你死背所有函数名，但要理解几个最重要的：
StrLength(S)求串长。
SubString(&Sub, S, pos, len)求子串。
Concat(&T, S1, S2)连接字符串。
Index(S, T)在 S 中寻找 T。
其中最重要的显然就是：
Index(S, T)因为整个第4章后半部分其实都在研究：
Index()怎样实现得更快？
四、串的三种存储结构
这一部分主要理解。
1. 定长顺序存储
本质就是数组：
#define MAXLEN 255
typedef struct {
char ch[MAXLEN];
int length;
} SString;字符连续存储。
例如：
下标：1 2 3 4 5
字符：a b c d e优点是简单、访问方便。
问题是数组容量固定。
例如 MAXLEN=255，结果串长度变成 300，就装不下。
资料将超出部分被舍弃的情况称为截断。
2. 堆分配存储
还是连续存储，但长度不是提前固定，而是在运行时动态申请：
typedef struct {
char *ch;
int length;
} HString;例如 C 中：
malloc()
free()所以：
定长顺序存储：数组提前固定
堆分配：运行时动态申请连续空间注意：
堆分配仍然是顺序存储，不是链式存储。
这一点和动态顺序表类似。
3. 块链存储
使用链表存串。
不过因为一个字符很小，如果每个结点只存一个字符：
[data|next]指针空间占比就太高。
所以经常一个结点放多个字符：
| a b c d | next |一个结点叫一个块。
这部分了解即可。
五、4.2 模式匹配——本章正式重点
从这里开始是考试重点。
六、朴素模式匹配算法
又叫简单模式匹配、暴力匹配、BF 算法。
假设：
主串 S = "ababcabcacbab"
模式 T = "abcac"核心思想非常直接：
从主串某个位置开始，把模式串一个字符一个字符往后比较。
如果全部相同，成功。
如果某个字符失败：
主串的匹配起点右移 1 位，模式串重新从第一个字符开始。
资料中的实现为：
int Index(SString S, SString T) {
int i = 1, j = 1;
while (i <= S.length && j <= T.length) {
if (S.ch[i] == T.ch[j]) {
++i;
++j;
} else {
i = i - j + 2;
j = 1;
}
}
if (j > T.length)
return i - T.length;
else
return 0;
}重点不是背代码，而是理解这一句：
i = i - j + 2;为什么是 i-j+2？
假设这一轮从主串第 start 个字符开始。
经过若干次成功比较后：
i = start + j - 1因此：
现在失配以后，要从下一个起点：
重新开始。
所以：
这就是那句代码的来源。
七、朴素匹配最大的问题：主串反复回退
例如：
主串：0000000000000000000001
模式：0000001可以发现每一次：
0 == 0
0 == 0
0 == 0
...
最后才失败然后：
主串起点只移动 1 位前面已经比较过的大量字符再次比较。
资料给出的结论是，若主串长度为 n，模式串长度为 m：
最多尝试：
个起点。
每个起点最多比较：
次。
因此最坏时间复杂度：
这就是 KMP 出现的原因。
八、KMP 到底解决了什么问题
KMP 的核心并不是“神奇地预测字符”。
它只是利用一个非常重要的事实：
前面已经匹配成功过的信息，不应该全部扔掉。
还是考虑：
主串：... a b c a X
模式： a b c a c前四个：
abca
abca已经确认相同。
第五个字符失配。
普通算法说：
全部作废！
主串回去重新匹配！KMP 则问：
已经成功匹配的
abca中，有没有某个“后缀”，恰好又是模式串的“前缀”？
如果有，我们就可以直接利用这段信息。
这就是 KMP 的灵魂。
九、理解 KMP 必须先搞清：前缀和后缀
假设字符串：
ababa前缀
必须从开头开始，但不能包含整个串：
a
ab
aba
abab后缀
必须到结尾结束，但不能包含整个串：
a
ba
aba
baba注意：
"bab"不是后缀，因为它没有一直延伸到末尾。
十、部分匹配值 PM
部分匹配值：
最长的“相等真前缀和真后缀”的长度。
对于：
ababa逐个看。
a
没有非空真前缀/后缀：
PM = 0ab
前缀：a
后缀：b没有相同：
PM = 0aba
前缀：a, ab
后缀：a, ba最长相同：
a长度 1：
PM = 1abab
前缀：a, ab, aba
后缀：b, ab, bab最长相同：
ab所以：
PM = 2ababa
最长相同前后缀：
aba所以：
PM = 3最终：
字符串：a b a b a
PM： 0 0 1 2 3十一、KMP 为什么可以根据 PM 跳跃
假设当前已经成功匹配了 q 个字符。
设这 q 个字符最长公共前后缀长度为 PM。
那么失配以后：
模式串前 PM 个字符已经和：
主串刚刚匹配部分的后 PM 个字符完全相等。
因此这 PM 个字符根本不需要再比较。
模式串右移：
即：
这就是 KMP 能跳过重复比较的根本原因。
十二、next 数组是什么——408最重要定义
现在进入最核心部分。
资料采用 从 1 开始编号 的标准形式：
当模式串第
j个字符发生失配时，next[j]表示下一次应该拿模式串的第几个字符与当前主串字符继续比较。
即：
失配：
S[i] != T[j]
KMP：
i 不变
j = next[j]这句话几乎必须刻进脑子里：
KMP 失配：主串指针
i不回退，模式串指针变为next[j]。
资料中的题目也直接考了这一点：若
那么下一轮就是模式串第 k 位与主串当前第 i 位对齐，答案就是 k。
十三、next 和 PM 的关系
如果采用资料中的 1 起始编号：
对于：
有：
为什么看 j-1？
因为：
第
j个字符还没匹配成功，它正是失配的位置。
所以只能利用：
第1 ～ 第j-1个字符这些已经成功的信息。
一个超级好用的手算办法
先写 PM：
PM：
0 0 1 2 3 ...然后：
整体向右移动一格 → 所有值加 1 → 第一格写 0 → 最后一项舍去。
例如模式串：
abcac各前缀 PM：
a 0
ab 0
abc 0
abca 1
abcac 0即：
PM = 0 0 0 1 0右移：
_ 0 0 0 1加 1：
_ 1 1 1 2第一项置 0：
next = 0 1 1 1 2所以：
字符： a b c a c
next： 0 1 1 1 2这就是考试最快的手算方法之一。
十四、重点例题：acaba 的 next
资料模拟题直接考：
模式串：acaba求 next。
使用 1 起始编号。
第1位
规定：
next[1] = 0第2位
第2位之前只有：
a没有可利用的非空前后缀：
next[2] = 1第3位
看前两个字符：
ac前后缀不相等：
next[3] = 1第4位
看：
aca最长相等前后缀：
a长度 1。
因此：
第5位
看：
acab没有非空相等前后缀：
next[5] = 1最终：
字符： a c a b a
next： 0 1 1 2 1即：
01121资料模拟题答案也是 C。
十五、为什么 next[1]=0？
这是人为规定的哨兵值。
如果：
S[i] != T[1]连模式串第一个字符都不相同，那模式串没有任何已经匹配成功的信息可以利用。
于是：
j = next[1] = 0随后主循环遇到：
j == 0执行：
++i;
++j;于是：
i → i+1
j → 1也就是说：
放弃当前主串字符，从主串下一个字符重新和模式串首字符比较。
十六、KMP代码应该怎么看，而不是死背
资料中的核心代码：
int Index_KMP(SString S, SString T, int next[]) {
int i = 1, j = 1;
while (i <= S.length && j <= T.length) {
if (j == 0 || S.ch[i] == T.ch[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j > T.length)
return i - T.length;
else
return 0;
}只需要抓住两条路径。
匹配成功
S[i] == T[j]那么：
i++;
j++;两边一起向后走。
匹配失败
S[i] != T[j]那么：
j = next[j];注意：
i 不动所以图像上不是主串回退，而是：
模式串向右滑十七、KMP 中一个非常高频的认知错误
很多人会想：
j变小了，是不是模式串向左移动？
不是。
因为模式串只是“逻辑对齐关系”发生变化。
例如原来：
i
主串： ......X
模式： abcde
j失配后：
j → next[j]同一个 S[i] 改为和模式串更靠前的字符比较：
i
主串： ......X
模式： abcde
j从整体位置看：
模式串实际上向右移动了。
十八、next 的递推构造——算法题理解重点
资料中的构造代码：
void get_next(SString T, int next[]) {
int i = 1, j = 0;
next[1] = 0;
while (i < T.length) {
if (j == 0 || T.ch[i] == T.ch[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}这个算法最容易看懵。
可以把它理解为：
“用模式串自己匹配自己。”
假设当前已经知道：
next[i] = j也就是：
T[1...j-1]等于：
T[i-j+1...i-1]现在要判断能不能再扩展一个字符。
比较：
T[i]
T[j]情况1：相等
如果：
T[i] == T[j]那么原来的最长公共前后缀可以再增加一个字符。
所以：
i++;
j++;
next[i] = j;本质就是：
情况2：不相等
如果：
T[i] != T[j]说明当前长度的前后缀没法继续。
但也不能直接判定为 0。
因为：
当前这个前缀本身可能还有更短的相等前后缀。
于是：
j = next[j];继续尝试更短的候选前缀。
这和真正的 KMP 匹配过程完全一样。
所以：
get_next()本质上也是 KMP 思想，只不过是在模式串内部寻找自己的前后缀结构。
十九、KMP 的时间复杂度
设：
主串长度 n
模式串长度 m计算 next：
真正匹配：
因此总复杂度：
而朴素算法最坏：
不过资料也提醒：普通数据下朴素算法平均性能往往没有最坏情况那么差，因此在实际简单场景中仍然很常见；KMP 最大优势是在字符串存在大量重复前后缀时避免重复比较。
二十、nextval——KMP的进一步优化
这是本章第二个高频难点。
资料标出了 nextval 为考点，并且模拟题专门考过。
先看模式：
aaaab普通 next：
字符： a a a a b
next： 0 1 2 3 4假设现在：
S[i] = b
T[4] = a失配。
普通 KMP：
j = next[4] = 3于是继续比较：
S[i] = b
T[3] = a肯定还是失败。
再：
j = next[3] = 2比较：
b vs a还失败。
再：
b vs a仍失败。
显然都是废操作。
二十一、为什么这些比较一定没意义
已经知道：
S[i] != T[j]如果同时：
T[j] == T[next[j]]那么必然：
S[i] != T[next[j]]因为：
T[j] 和 T[next[j]]根本就是同一个字符。
所以没必要再比较一次。
因此：
如果回退到的位置上的字符和当前失配字符相同，就继续往更前面跳。
这就是 nextval。
二十二、nextval 的核心规则
普通：
next[j] = k如果：
T[j] != T[k]这个 k 是有效的：
nextval[j] = k如果：
T[j] == T[k]那么跳到 k 还是必错。
所以：
nextval[j] = nextval[k]即：
继续跳直到找到：
字符不同或者：
到达 0二十三、例子：aaaab
资料给出的结果：
字符： a a a a b
next： 0 1 2 3 4
nextval： 0 0 0 0 4为什么前四个全是 0？
例如第4位：
T[4] = a
next[4] = 3
T[3] = a相同。
所以不能停在 3。
继续：
next[3] = 2
T[2] = a仍相同。
继续。
最终一路跳到 0。
因此：
nextval[4] = 0二十四、nextval 构造代码怎么理解
资料代码：
void get_nextval(SString T, int nextval[]) {
int i = 1, j = 0;
nextval[1] = 0;
while (i < T.length) {
if (j == 0 || T.ch[i] == T.ch[j]) {
++i;
++j;
if (T.ch[i] != T.ch[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
} else {
j = nextval[j];
}
}
}最核心就两句：
if (T.ch[i] != T.ch[j])
nextval[i] = j;字符不同，可以放心跳到 j。
否则：
nextval[i] = nextval[j];字符相同，跳到 j 也必然再次失配，所以进一步跳。
二十五、一个非常重要的问题：为什么你有时看到 next[0]=-1？
这是 KMP 最容易让学生混乱的地方。
资料主体采用：
字符串从 1 开始
next[1] = 0例如：
acaba
next = 0 1 1 2 1但另一种常见教材/代码采用：
字符串从 0 开始
next[0] = -1例如模拟题里就出现：
ababac
next =
[-1, 0, 0, 1, 2, 3]以及：
nextval =
[-1, 0, -1, 0, -1, 3]资料中的模拟题就是这种 0 下标表示法。
两者不是两个不同的 KMP。
只是下标体系不同。
大致关系可以理解为：
1-based：
next[1] = 0
0-based：
next[0] = -1所以考试时第一件事：
先看题目采用 0 下标还是 1 下标。
千万不要把两套 next 定义混着算。
二十六、一道资料中的典型 nextval 题
资料模拟题：
主串：
aabaabcabc
模式串：
aaabc采用 0 起始的 nextval 表示。
题目告诉你：
i = 2
j = 2发生失配。
此时模式串前面连续都是：
a a a如果普通 next 不断回退：
还是拿 b 和 a 比
还是失败nextval 会直接跳过这些必然失败的位置。
资料给出的：
nextval[2] = -1失配后：
j = -1KMP 的特殊规则使：
i++;
j++;于是下一次真正比较时：
i = 3
j = 0因此答案为 C。
二十七、408 常考什么？重点练习四类题
结合这里的资料和选择题，这章的题型非常固定。
| 题型 | 重要程度 | 典型问法 |
|---|---|---|
next 数组手算 | ★★★★★ | 给模式串求 next |
nextval 手算 | ★★★★★ | 给 next 求 nextval |
失配后的 i,j | ★★★★★ | 失配后下一次比较哪两个字符 |
| 比较次数 | ★★★★☆ | KMP 成功前一共字符比较几次 |
| KMP 原理 | ★★★★☆ | 为什么主串不回退 |
| BF 与 KMP 复杂度 | ★★★☆☆ | 最坏复杂度比较 |
| 串的存储结构 | ★★☆☆☆ | 定长/堆/块链特点 |
| 串基本操作 | ★☆☆☆☆ | 概念性选择题 |
二十八、遇到“求 next”题，建议固定使用这个流程
以模式串：
P = p1 p2 ... pm为例。
考试时不要凭感觉乱跳。
固定这么做：
第一步：确定编号体系。
如果：
next[1]=0就是 1-based。
如果：
next[0]=-1就是 0-based。
第二步：求当前位置之前的最长相等真前后缀。
对于第 j 个字符失配，看的不是包含第 j 个字符的全部串，而是：
P[1 ... j-1]第三步：转换为 next。
1-based 下：
特殊：
这种方法做选择题通常比模拟代码稳定得多。
二十九、遇到“求 nextval”题，固定这样做
先把普通 next 算出来。
然后逐个位置检查：
假设：
next[j] = k如果：
P[j] != P[k]那么：
nextval[j] = k否则：
P[j] == P[k]就跳过：
nextval[j] = nextval[k]一句话记忆：
next找“能去哪”；nextval再排除“去了也必错”的位置。
三十、遇到“比较次数”题，千万别只看指针移动次数
每执行一次：
S[i] == P[j] ?或者：
S[i] != P[j] ?都算一次字符比较。
但：
j = next[j]本身不是字符比较。
同理：
j == -1这种哨兵判断，也通常不算字符串字符之间的比较。
最稳妥的方法是做一个表：
当前 i | 当前 j | 比较字符 | 成功/失败 | 下一状态 |
|---|---|---|---|---|
| 0 | 0 | S[0] vs P[0] | × | ... |
| ... | ... | ... | ... | ... |
每一行有真正字符比较就加 1。
这样不容易漏。
三十一、最容易错的几个点
1. 把“子串”和“子序列”混淆
子串必须连续。
abcdebcd 是子串。
ace 不是子串。
2. 把空串和空格串混淆
"" 长度0
" " 长度13. 求 next[j] 时把第 j 个字符也算进去了
第 j 个字符已经失配。
所以应该分析的是：
P[1 ... j-1]4. 把前缀/后缀算成整个字符串
所谓真前缀、真后缀：
不能等于整个字符串本身。
否则任何字符串和自己都相等，PM 就没有意义了。
5. 认为 KMP 的主串完全不会向前走
准确说：
发生失配时
i不回退。
成功比较时：
i++模式首字符都失配时，最终也会：
i++6. 把 next[i] 当成和主串有关
next 是：
只根据模式串本身计算出来的。
它与主串内容没有关系。
这是资料选择题直接考察的点。
7. 混用两套下标体系
这是最危险的。
1-based：
next[1]=0
0-based：
next[0]=-1题目给哪个，就按哪个来。
三十二、你应该怎样真正理解 KMP
不要把 KMP 理解成：
“失配以后查一个神秘的 next 表。”
应该把它理解为下面这个逻辑。
假设已经成功匹配：
P[1 ... j-1]现在：
S[i] != P[j]于是问：
已经匹配的这一段结尾，有没有一部分恰好和模式串开头一样？
如果有：
前缀
abc
P = abc......abcX
后缀那么因为这个“后缀”在主串中已经匹配成功：
主串：......abcX
模式：abc......X根本不需要重新比较 abc。
直接让：
模式前缀 abc和：
已经成功的主串后缀 abc对齐即可。
所以真正决定 KMP 跳转位置的是：
最长相等前缀和后缀。
next 只是把这条规律提前计算成了数组。
这才是 KMP 的本质。
三十三、本章考研复习优先级
最后给你压缩成一个复习版本。
第一优先级：必须熟练
KMP 原理
必须会回答：
为什么
i可以不回退？
因为已匹配串的最长后缀可与模式串最长前缀重新对齐。
next 手算
至少做到看到：
acaba
abaabcaba
ababac这类串能稳定算出 next。
nextval
知道优化条件：
P[j] == P[next[j]]时普通 KMP 会发生必然重复失配，应继续跳。
失配后的指针变化
普通 KMP：
j = next[j];优化 KMP：
j = nextval[j];主串 i 在普通失配时不回退。
第二优先级：会做题
比较次数、模式串移动距离、匹配成功位置、0/1 下标体系转换。
第三优先级：理解即可
串基本操作、定长顺序存储、堆分配、块链存储。
因为你这份资料自己也明确指出：统考考纲核心是字符串模式匹配，重点是 KMP、next 和 nextval 的推导。
三十四、一页式记忆
可以最后只记住下面这个关系链：
BF：
失配
→ 主串回退
→ 模式串回到开头
→ 重复比较多
→ 最坏 O(nm)
KMP：
失配
→ 主串 i 不回退
→ j = next[j]
→ 利用已匹配信息
→ O(n+m)
为什么能跳？
→ 已匹配序列存在
“后缀 = 模式串前缀”
PM：
最长相等真前后缀长度
1-based：
next[1] = 0
next[j] = PM[j-1] + 1
nextval：
如果 P[j] == P[next[j]]
→ 跳到 next[j] 仍必然失配
→ 继续跳
→ nextval[j] = nextval[next[j]]第4章真正做到“会”的标准不是背出 KMP 代码，而是给定任意一个模式串，你能解释为什么某个位置的 next 是那个值；给你一次失配，你能准确说出主串为什么不动、模式串为什么跳到那个位置。做到这一点，nextval 和比较次数题也就会顺很多。