第4章串（自学增强版）¶

章节定位：算法技巧章

这一章的核心不是串本身，而是模式匹配思想，尤其是 BF 与 KMP 的差异。
建议把 next 数组、nextval 数组和 KMP 过程手推一遍，再回到代码页逐行核对。

1. 本章定位¶

这一章看起来篇幅不大，但它的地位很特别：它是“线性结构思想”第一次真正落到文本处理上的一章。
前面我们学线性表、栈、队列时，处理对象大多是“一个一个元素”；到了串，处理对象变成了“一个连续的字符序列”，所以很多操作不再围绕单个元素，而是围绕“子串”展开。

这一章最核心的任务有两个：

搞清楚串是什么、和线性表像在哪里、又不同在哪里。
真正理解模式匹配，尤其是 KMP 为什么能让主串指针不回溯。

如果这一章吃透了，后面学搜索、编译原理、文本处理、搜索引擎、编辑器、正则相关内容时，都会轻松很多。

2. 学习目标¶

学完本章后，你应该能做到：

说清楚串、空串、空格串、子串、主串、位置、串长这些概念。
解释为什么串的逻辑结构和线性表相似，但基本操作的关注点不同。
看懂并实现串的顺序存储和堆分配存储。
独立写出串的赋值、复制、比较、求长、取子串、连接等基本操作。
说清楚朴素模式匹配 BF 算法的流程、回溯发生在哪里、复杂度为什么是 O(nm)。
理解 KMP 的本质：利用模式串自身结构，避免主串指针回退。
会求 PM 表、next 数组、nextval 数组，并能手工模拟匹配过程。
能把教材伪代码落实成真实 C 代码。

3. 本章结构总览¶

本章按知识脉络可以分成四层：

先认识“串到底是什么”。
再看“串在内存里怎么存”。
接着看“怎么在主串里找模式串”。
最后把“朴素匹配”升级成 KMP。

你可以把这一章理解成一个逐步升级的故事：

一开始：我只是想在一段文本里找某个词。
朴素做法：从头一个个试，失败了就从下一个位置重新试。
问题出现：很多比较明明是重复的。
升级思路：既然重复比较来自模式串本身，那就提前研究模式串的结构。
最终结果：主串不回退，匹配效率大幅提高。

4. 4.1 串的定义和实现¶

4.1 串的定义¶

串（String）是由零个或多个字符组成的有限序列。

形式上我们常写成：

S = 'a1a2a3...an'

这里：

S 是串名。
引号中的字符序列是串值。
字符个数 n 是串长。
当 n = 0 时，这个串叫空串。

4.2 必须分清的几个概念¶

4.2.1 串长¶

串长就是字符个数。

例如：

'China' 的串长是 5
'Beijing' 的串长是 7
'' 的串长是 0

4.2.2 空串 vs 空格串¶

这是最容易混淆的点之一。

空串：一个字符都没有，长度为 0。
空格串：由一个或多个空格字符组成，长度大于 0。

形象理解：

空串像“盒子里什么都没有”。
空格串像“盒子里放了几张白纸”，你肉眼容易觉得“像空的”，但它其实占位置。

4.2.3 子串与主串¶

一个串中任意连续的一段字符序列，叫这个串的子串。
包含该子串的原串，叫主串。

例如：

A = 'China Beijing'
B = 'Beijing'
C = 'China'

那么：

B 是 A 的子串。
C 也是 A 的子串。
A 是 B 和 C 的主串。

注意关键词是“连续”。
如果字符不连续，就不能叫子串。

4.2.4 位置¶

某字符在串中的序号，叫它在串中的位置。
子串在主串中的位置，通常指子串第一个字符在主串中出现的位置。

教材里常用 位序从 1 开始。
而真实 C 代码里数组下标从 0 开始。
这就是学习串时的第一个“翻译工作”。

4.3 串和线性表有什么关系¶

串的逻辑结构和线性表非常像，因为它们本质上都是“有限序列”。

但两者关注点不同：

线性表更关注单个元素。
串更关注连续的一段字符，也就是子串。

举例：

线性表常做：插入某个元素、删除某个元素、按位查找。
串常做：查找某个子串、截取某个子串、比较两个串。

一句话总结：

线性表是“一个一个元素地处理”。
串是“按片段处理”。

4.4 串的基本操作¶

教材给出的常见基本操作包括：

StrAssign(&T, chars)：赋值
StrCopy(&T, S)：复制
StrEmpty(S)：判空
StrCompare(S, T)：比较
StrLength(S)：求串长
SubString(&Sub, S, pos, len)：取子串
Concat(&T, S1, S2)：连接
Index(S, T)：定位或模式匹配
ClearString(&S)：清空
DestroyString(&S)：销毁

其中最核心的“最小操作子集”通常是：

赋值
比较
求长
连接
取子串

原因很简单：

这些是基础积木。
其他很多操作都能由它们再组合出来。

4.5 串的存储结构¶

4.5.1 定长顺序存储¶

最直接的想法是：给串一段连续空间，用数组存字符，再额外保存串长。

教材经典定义可以整理成：

#define MAX_STR_LEN 255

typedef struct {
    char ch[MAX_STR_LEN + 1];
    int length;
} SString;

它的特点是：

存储连续，访问方便。
实现简单，适合教材讲解。
最大长度固定，超过上限就要截断。

这里的 +1 往往是为了给 '\0' 预留空间，方便和 C 字符串接口配合。

4.5.2 堆分配存储¶

如果不想把最大长度写死，就可以动态分配：

typedef struct {
    char *ch;
    int length;
} HString;

它的特点是：

长度更灵活。
内存按需申请。
必须自己管理生命周期，记得 free。

形象理解：

定长顺序存储像“提前租好一间固定大小的仓库”。
堆分配像“需要多大就临时租多大”。

4.5.3 块链存储¶

教材还提到块链存储，但通常只做了解。

它的思想是：

一个结点不一定只放一个字符。
一个结点可以放多个字符，整个串由多个块连起来。

它的意义在于：

兼顾链式结构与批量存储。
但在考研和基础实现里，重点一般还是顺序存储和模式匹配。

4.6 真实代码：串的基本操作¶

本章真实代码文件在：

第4章普通代码版

已经实现的核心函数包括：

InitSString
StrAssignSString
StrCopySString
StrEmptySString
StrCompareSString
StrLengthSString
SubStringSString
ConcatSString
ClearStringSString
InitHString
StrAssignHString
DestroyHString

你可以把它们和教材中的抽象操作一一对应起来看。

例如，教材里的：

StrAssign(&T, chars)

在真实代码里对应的是：

bool StrAssignSString(SString *str, const char *chars)

这就是“教材伪代码 -> 可运行 C 代码”的典型转换。

4.7 伪代码与真实代码对照：取子串¶

原书思路版伪代码¶

SubString(&Sub, S, pos, len)
1. 若 pos 非法，或 pos + len - 1 超界，则失败
2. 从 S 的第 pos 个字符开始，复制 len 个字符到 Sub
3. 修改 Sub 的长度
4. 返回成功

对应真实代码¶

bool SubStringSString(SString *sub, const SString *source, int pos, int len) {
    if (sub == NULL || source == NULL || pos < 1 || len < 0) {
        return false;
    }
    if (pos > source->length || pos + len - 1 > source->length) {
        return false;
    }

    memcpy(sub->ch, source->ch + pos - 1, (size_t)len);
    sub->ch[len] = '/0';
    sub->length = len;
    return true;
}

理解重点¶

教材位序从 1 开始，所以真实代码里要写 pos - 1。
memcpy 是在“整段复制”，这比一个字符一个字符写更简洁。
复制完之后要补 '\0'，这样 printf("%s") 才能正常打印。

5. 4.2 串的模式匹配¶

5.1 模式匹配到底在做什么¶

模式匹配就是：

在主串中查找与模式串相同的子串，并返回它第一次出现的位置。

比如：

主串   S = 'ababcabcacbab'
模式串 T = 'abcac'

我们要做的事就是：
在 S 里找到第一个和 T 完全一样的连续片段。

5.2 朴素模式匹配 BF 的思想¶

BF（Brute Force）也叫暴力匹配。

它的思路特别直观：

让主串当前位置和模式串第一个字符比。
如果相等，就继续往后逐个比较。
一旦失配，就把模式串整体右移一位，从头再试。

这就像你拿着一张透明小纸条去对齐一篇文章：

先对准第一列。
一旦某个字符对不上，就把小纸条往右挪一格。
再从头对一次。

原书思路版伪代码¶

Index(S, T)
i = 1, j = 1
while i <= S.length and j <= T.length
    if S[i] == T[j]
        i++, j++
    else
        i = i - j + 2
        j = 1
if j > T.length
    return i - T.length
else
    return 0

对应真实代码¶

int IndexBF(const SString *main_str, const SString *pattern) {
    int i = 1;
    int j = 1;

    if (main_str == NULL || pattern == NULL || pattern->length == 0) {
        return 0;
    }

    while (i <= main_str->length && j <= pattern->length) {
        if (main_str->ch[i - 1] == pattern->ch[j - 1]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }

    if (j > pattern->length) {
        return i - pattern->length;
    }
    return 0;
}

为什么 `i = i - j + 2`¶

这行是很多同学第一次看会卡住的地方。

它的含义是：

i 当前已经走到了失配位置。
j 表示模式串已经匹配了多少位。
失配后，主串的新起点应该回到“本趟起点的下一位”。

如果本趟从主串第 k 位开始，那么失配时有：

k = i - j + 1

所以下一趟起点就是：

k + 1 = i - j + 2

这就是公式来源。

5.3 BF 为什么慢¶

问题出在“重复比较”。

当一趟匹配失败时：

主串指针会回退到某个旧位置。
模式串又会从头开始比较。
前面明明已经比较过的字符，可能又被重复比较一遍。

所以最坏情况下时间复杂度是：

O(nm)

其中：

n 是主串长度。
m 是模式串长度。

如果主串很长、模式串也不短，而且前面大量字符都很像，那么 BF 会非常吃亏。

6. KMP：真正的重点¶

6.1 KMP 在解决什么问题¶

KMP 的目标不是“让模式串少动一点”，而是：

在失配时，不让主串指针回退。

这才是它最值钱的地方。

为什么能做到？

因为 KMP 提前研究了模式串自己的结构：

哪些前缀和后缀相等？
失配后模式串应该跳到哪里继续比较？

换句话说：

BF 是“失败了就回头重试”。
KMP 是“失败了，但我知道哪里不用再试”。

6.2 前缀、后缀、部分匹配值 PM¶

要学 KMP，先把三个概念打牢：

前缀¶

除最后一个字符外，串的所有头部子串。

后缀¶

除第一个字符外，串的所有尾部子串。

部分匹配值 PM¶

某个串的“最长相等前后缀”的长度。

例如模式串 ababa：

'a' 的 PM 值是 0
'ab' 的 PM 值是 0
'aba' 的 PM 值是 1
'abab' 的 PM 值是 2
'ababa' 的 PM 值是 3

所以它的 PM 表是：

0 0 1 2 3

形象理解：

PM 值回答的是：“当前这段串，头和尾最多能重合多少个字符？”

6.3 KMP 的直觉版解释¶

假设我们正在匹配：

主串   ababcabcacbab
模式串 abcac

某一刻前面已经成功匹配了一段，但后面失配了。
这时 BF 会把模式串右移一位，从头开始。
而 KMP 会想：

既然前面这几位已经相等，
那么模式串前面某一部分和后面某一部分其实已经对齐过了，
其中有些比较没必要再来一遍。

所以：

主串停在当前失配位置。
模式串根据 next 数组跳转到合适位置。
继续比较。

这就是“主串不回溯”的本质。

6.4 next 数组是什么¶

教材常用的定义是：

当模式串第 j 个字符失配时，下一个应该与主串当前字符比较的是模式串的第 next[j] 个字符。

这里的 next[j] 本质上是在说：

“别回到模式串开头瞎试了，直接跳到这个位置继续。”

如果模式串是 abcac，教材风格下可得到：

next = [0, 1, 1, 1, 2]

这和本章真实代码运行结果一致。

6.5 PM 表与 next 数组的关系¶

这也是高频考点。

在教材常见的 1-based 写法下：

next[j] = PM[j - 1] + 1

其中：

PM[j - 1] 表示前 j - 1 个字符的最长相等前后缀长度。
+1 是因为教材用的是“位序”而不是 0-based 下标。

所以学习时你要养成一个习惯：

先分清教材是从 1 还是从 0 开始编号。
再看公式。
不要死背一个“孤立的 next 数组结果”。

6.6 原书伪代码与真实代码对照：求 next 数组¶

原书思路版伪代码¶

get_next(T, next)
i = 1, j = 0
next[1] = 0
while i < T.length
    if j == 0 or T[i] == T[j]
        i++, j++
        next[i] = j
    else
        j = next[j]

对应真实代码¶

bool GetNextArray(const SString *pattern, int *next) {
    int i = 1;
    int j = 0;

    if (pattern == NULL || next == NULL || pattern->length <= 0) {
        return false;
    }

    next[1] = 0;
    while (i < pattern->length) {
        if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return true;
}

理解重点¶

i 负责向前扩展“当前已经求出的前缀长度”。
j 负责表示“当前可复用的最长相等前后缀长度”。
如果 pattern[i] == pattern[j]，说明可复用长度继续增长。
否则就沿着 next[j] 继续回跳，找更短但仍可能复用的前后缀。

这段代码的灵魂不是“背循环”，而是：

失配时，不是重头开始，而是跳到“次优但仍有希望”的位置。

6.7 KMP 匹配伪代码与真实代码¶

原书思路版伪代码¶

Index_KMP(S, T, next)
i = 1, j = 1
while i <= S.length and j <= T.length
    if j == 0 or S[i] == T[j]
        i++, j++
    else
        j = next[j]
if j > T.length
    return i - T.length
else
    return 0

对应真实代码¶

int IndexKMP(const SString *main_str, const SString *pattern, const int *next) {
    int i = 1;
    int j = 1;

    if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
        return 0;
    }

    while (i <= main_str->length && j <= pattern->length) {
        if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }

    if (j > pattern->length) {
        return i - pattern->length;
    }
    return 0;
}

关键观察¶

BF 失配时改的是 i 和 j。
KMP 失配时通常只改 j。
这就意味着主串指针 i 不回退。

所以 KMP 的时间复杂度是：

O(n + m)

6.8 nextval 为什么还要再优化一次¶

next 已经很好了，但还不够极致。

问题场景是：

如果失配后跳到的那个位置，字符和当前失配字符还是一样，
那下一次比较其实还是注定失败，这就形成了“无意义比较”。

于是引入 nextval：

如果 pattern[i] != pattern[j]，就保留原来的跳转。
如果 pattern[i] == pattern[j]，就继续递归压缩跳转位置。

这样做的意义是：

减少“跳了，但还是立刻失败”的重复比较。

对应真实代码¶

bool GetNextValArray(const SString *pattern, int *nextval) {
    int i = 1;
    int j = 0;

    if (pattern == NULL || nextval == NULL || pattern->length <= 0) {
        return false;
    }

    nextval[1] = 0;
    while (i < pattern->length) {
        if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
            i++;
            j++;
            if (pattern->ch[i - 1] != pattern->ch[j - 1]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
    return true;
}

7. 真实代码运行结果与知识点对应¶

本章代码已经真实编译并运行通过，对应可执行文件为：

本章示例程序

当前已经验证的内容包括：

顺序串赋值、复制、判空、比较、求长、连接、取子串
堆分配串初始化、赋值、销毁
BF 模式匹配
next 数组求解
nextval 数组求解
KMP 匹配
模式串出现次数统计

其中一个很适合自学观察的对比例子是：

主串: "aaaaa"
模式串: "aa"

代码里分别给出了：

不重叠匹配次数：2
允许重叠匹配次数：4

这可以帮助你区分两个常被混用的问题：

“能匹配几次”
“能找到几个起始位置”

8. 高频易错点¶

8.1 空串不等于空格串¶

空串长度是 0，空格串长度大于 0。

8.2 子串必须连续¶

不连续只能叫子序列，不能叫子串。

8.3 教材位序和代码下标混淆¶

教材多用 1-based，代码多用 0-based。
如果你把这两个体系混在一起，next、SubString、KMP 都会错。

8.4 KMP 的关键不是“模式串滑动很聪明”¶

真正关键是：

主串不回退。

8.5 next 和 nextval 不要混记¶

next：基本跳转规则。
nextval：在 next 基础上进一步消除无意义比较。

9. 刷题与自学建议¶

学习顺序建议按下面来：

先把串的定义、空串、子串、主串这些概念背扎实。
再把顺序存储和堆分配存储看懂。
然后手模拟 BF。
再去学前缀、后缀、PM。
最后再学 next、KMP、nextval。

如果顺序反了，常见后果是：

会背 KMP 代码，但不知道它为什么这样跳。

那样一到手算题、比较次数题、next 推导题就容易崩。

10. 本章小结¶

这一章表面上在讲“字符序列”，本质上在讲“如何利用已知信息避免重复工作”。

你可以把整章压缩成这几句话：

串是特殊的线性结构，重点操作对象是子串。
串可以顺序存储，也可以动态分配。
BF 会重复比较，所以最坏复杂度是 O(nm)。
KMP 通过分析模式串本身结构，让主串不回退。
PM、next、nextval 都是在服务“跳过无意义比较”这件事。

11. 当前版本完成度¶

本章当前已经完成的部分：

章节主干知识讲解
串的基本概念与存储结构
BF、KMP、next、nextval 的核心解释
原书思路版伪代码与真实 C 代码对照
可编译可运行的代码文件

后续继续加厚时，优先补这几块：

逐行拆解 GetNextArray
逐行拆解 IndexKMP
本章题型索引
本章自学检查清单
原书试题区的系统整理版

至此，第 4 章的主干内容、代码和题解框架已经建立起来。

12. 代码阅读入口¶

建议按下面的顺序阅读第 4 章代码：

先读 第4章普通代码版 里的 IndexBF
再读 第4章普通代码版 里的 GetNextArray
接着读 第4章普通代码版 里的 IndexKMP
最后再读 第4章普通代码版 里的 GetNextValArray

为什么这样安排：

BF 负责告诉你“原始做法哪里慢”。
GetNextArray 负责告诉你“KMP 预处理时到底算了什么”。
IndexKMP 负责告诉你“匹配阶段到底怎样用 next 跳”。
GetNextValArray 是在 next 基础上的进一步优化。

一上来就死盯 IndexKMP，很容易看得一头雾水。
因为 IndexKMP 的每一次跳转，都依赖你先理解 next 数组的含义。

13. 逐行拆解：GetNextArray¶

对应源码位置：

第4章普通代码版（约第203行）

原函数如下：

bool GetNextArray(const SString *pattern, int *next) {
    int i = 1;
    int j = 0;

    if (pattern == NULL || next == NULL || pattern->length <= 0) {
        return false;
    }

    next[1] = 0;
    while (i < pattern->length) {
        if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return true;
}

13.1 先说整体任务¶

这个函数的任务不是“去主串里找模式串”，而是：

提前研究模式串本身，算出失配时该往哪里跳。

所以它是在做“预处理”。

你可以把它理解成：

BF 是临场硬试。
KMP 是先做一份跳转备忘录，再去匹配。

GetNextArray 生成的，就是这份备忘录。

13.2 逐行理解¶

bool GetNextArray(const SString *pattern, int *next) {

这一行是在定义函数：

输入是模式串 pattern
输出写入数组 next
返回值是 bool
true 表示求解成功，false 表示输入不合法

    int i = 1;
    int j = 0;

这里最关键。

i 表示“当前准备求哪个位置的 next 值”
j 表示“当前已经找到的可复用前后缀长度所对应的比较位置”

教材这里采用的是 1-based 思维，所以：

i = 1 表示从模式串第 1 个字符开始考虑
j = 0 不是有效字符位置，而是一种“已经退无可退”的特殊状态

这也是后面经常出现 j == 0 判断的原因。

    if (pattern == NULL || next == NULL || pattern->length <= 0) {
        return false;
    }

这一段是输入合法性检查。

它在防三种问题：

模式串指针为空
输出数组指针为空
模式串长度非法

如果不先挡住这些情况，后面数组访问就有风险。

    next[1] = 0;

这行是整个 next 数组的起点。

含义是：

如果模式串第 1 个字符就失配
那么模式串没办法再往自身内部跳
只能让匹配流程进入“主串后移一位，模式串重新从头开始”的状态

所以教材写成 next[1] = 0。

这不是随便规定的，而是为了表达：

第一个字符失配时，已经没有更短的前后缀可用了。

    while (i < pattern->length) {

这个循环表示：

只要还没把整个模式串的 next 都求完
就继续往后推

注意这里不是 <=，因为循环体里会先 i++，再写 next[i]。

        if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {

这行是灵魂判断。

分成两种情况：

j == 0
表示已经退回到头了
说明当前没有更短前后缀可继续尝试
这时只能把 i、j 一起往前推进
pattern->ch[i - 1] == pattern->ch[j - 1]
表示当前扩展后的字符仍然相等
说明“最长相等前后缀”可以继续延长

这里的 i - 1 和 j - 1，是因为：

逻辑上用的是第 i 位、第 j 位
数组实际下标从 0 开始

            i++;
            j++;

这一组动作表示：

当前条件成立
那么前后缀匹配长度可以一起向后扩展一位

形象理解：

原来前后缀能重合到某个长度
现在又多对上了一个字符
所以“可复用长度”增加了

            next[i] = j;

这行是在记录结果。

含义是：

模式串第 i 位失配时
下一次应跳到模式串第 j 位继续比较

也可以理解成：

当前已经算出了 next[i]
这个值来源于前面那段“最长相等前后缀”的长度信息

        } else {
            j = next[j];
        }

这段非常关键。

意思不是“失败了重新开始”，而是：

当前 j 这个候选长度不行
那就别回到最开始
而是跳到“更短但仍可能可用”的那个位置

这正是 KMP 思想最核心的地方：

失败后不是清空记忆
而是复用次优解

    }
    return true;
}

循环结束，说明所有 next 值都已经算完，返回成功。

13.3 这一段最容易卡住的点¶

为什么 `j = next[j]` 不会乱掉¶

因为 next[j] 的定义本来就是：

如果模式串第 j 位失配
那么下一次最合适跳到哪里

所以这里本质上是在“沿着失配链不断回退”，直到找到能继续对上的位置。

为什么 `j == 0` 时要特殊处理¶

因为这表示：

已经找不到任何可复用的前后缀
只能从头重新建立匹配

但这里的“从头”不是回到主串旧位置，而是给后续匹配逻辑一个重新起步的信号。

13.4 一句话记忆¶

GetNextArray 的本质就是：

用已经求出的 next 值，去加速后面 next 值的求解。

它自己就在实践“KMP 式复用”。

14. 逐行拆解：IndexKMP¶

对应源码位置：

第4章普通代码版（约第251行）

原函数如下：

int IndexKMP(const SString *main_str, const SString *pattern, const int *next) {
    int i = 1;
    int j = 1;

    if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
        return 0;
    }

    while (i <= main_str->length && j <= pattern->length) {
        if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }

    if (j > pattern->length) {
        return i - pattern->length;
    }
    return 0;
}

14.1 先说整体任务¶

这个函数就是正式执行 KMP 匹配的地方。

它要做的是：

拿着主串往前扫
拿着模式串同步比较
一旦失配，就利用 next 跳转
整个过程中尽量不让主串回退

14.2 逐行理解¶

int IndexKMP(const SString *main_str, const SString *pattern, const int *next) {

这一行说明：

输入有主串、模式串、next 数组
输出是匹配成功时的起始位置
如果失败则返回 0

    int i = 1;
    int j = 1;

这里：

i 指向主串当前比较位置
j 指向模式串当前比较位置

一开始都从第 1 位出发。

    if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
        return 0;
    }

先做输入检查，避免空指针或空模式串带来无意义操作。

    while (i <= main_str->length && j <= pattern->length) {

这个循环表示：

只要主串还没扫完
且模式串也还没全部匹配完成
就继续比较

        if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {

这行也是灵魂判断。

分两种情况：

j == 0
说明模式串已经退到最前面还没法继续复用
那就让主串和模式串都往前走一步，重新开始
两字符相等
说明本轮匹配继续成功
主串和模式串一起向后推进

            i++;
            j++;

这两行代表“当前比较成功，进入下一位比较”。

无论是：

真正字符相等
还是 j == 0 后重新起步

都要把当前位置推进。

        } else {
            j = next[j];
        }

这一段就是 KMP 最值钱的地方。

当失配时：

主串指针 i 不动
模式串指针 j 跳到 next[j]

也就是说：

主串当前这个字符还值得再比
但不需要再和模式串开头那些“已知不可能”的位置比较

这就是为什么 KMP 比 BF 更聪明。

BF 的反应是：

“我前面全白比了，再来一遍。”

KMP 的反应是：

“前面不全白比，我知道哪段可以直接复用。”

    if (j > pattern->length) {
        return i - pattern->length;
    }

如果 j 已经越过模式串末尾，说明模式串已经完整匹配成功。

为什么返回 i - pattern->length？

因为：

此时 i 已经指向“匹配结束位置的下一位”
所以起始位置要往前退回整个模式串长度

    return 0;
}

如果循环结束仍没匹配完整，就返回 0。

14.3 这里最容易误解的点¶

为什么失配时 `i` 不动¶

因为当前主串字符还没“用尽”。

它只是和当前的模式串位置不匹配，
但它可能和模式串中更靠前、由 next 指定的位置匹配。

所以不能急着把主串往后丢。

为什么 `j` 会突然跳很远¶

因为 next[j] 记录的不是“上一个位置”，而是：

在当前失配场景下
下一个最值得尝试的位置

这是一种基于模式串结构的跳转，不是随便回退。

14.4 一句话记忆¶

IndexKMP 的本质就是：

主串尽量只向前走，模式串负责智能回跳。

15. 把 GetNextArray 和 IndexKMP 连起来看¶

很多同学的问题不是单独看不懂某个函数，而是：

看得懂 GetNextArray
也看得懂 IndexKMP
但不知道两者怎么连起来

真正的关系是：

GetNextArray 先算好“失配时模式串怎么跳”
IndexKMP 在运行时直接拿这张跳转表用

你可以把它理解成：

GetNextArray 是赛前做战术板
IndexKMP 是比赛时按战术板执行

如果没有 GetNextArray，IndexKMP 根本不知道失配时该跳到哪里。
如果只有 GetNextArray，但没有 IndexKMP 去使用它，那也只是纸上谈兵。

16. 手推 KMP 时的固定步骤¶

手算 next 或模拟 KMP 时，建议固定按这个流程：

先明确题目位序是从 0 开始还是从 1 开始
先写模式串的各个前缀
再求每一段的最长相等前后缀长度
再由 PM 或定义推 next
最后再模拟 KMP 的 i、j 变化

模拟匹配时，每次只问自己两个问题：

当前两字符相等吗
如果不相等，j 应该跳到哪里

不要一上来就死背大段代码。
你只要一直抓住这两个问题，KMP 就不会丢。

19. 原书试题区整理版¶

这一部分不是简单把题目再抄一遍，而是按“考什么、怎么想、哪里最容易错”重新整理。
这样你后面刷题时，不用每次都从零散题目里重新摸规律。

19.1 单项选择题高频考点整理¶

题型1：什么叫模式匹配¶

这类题会问：

求子串是什么
模式匹配是什么
两者区别在哪里

正确抓法是：

求子串：从已知串里截出一段
模式匹配：在主串里寻找与模式串相同的子串

一句话区分：

求子串是“截”
模式匹配是“找”

题型2：KMP 中主串指针的性质¶

这类题特别爱问：

采用 KMP 匹配时，主串指针会不会回退？

答案核心只有一句：

主串指针不会回退
失配时主要调整的是模式串指针

所以如果题目写成选择项，一般应抓住：

主串指针不会变小

题型3：BF 和 KMP 的时间复杂度¶

这一类是最基础、也最爱考的。

你要记住：

朴素模式匹配 BF 最坏时间复杂度：O(nm)
KMP 时间复杂度：O(n + m)

但有一个容易掉坑的点：

实际运行中，BF 未必总是很慢
可一旦题目问“理论最坏时间复杂度”，你就必须答 O(nm)

题型4：KMP 失配时，i 和 j 怎么变¶

这是很多选择题的核心考点。

记忆方式如下：

若当前字符匹配成功：i++，j++
若失配：i 不变，j = next[j]
若 j == 0：说明模式串已经退到最前面，再令 i++，j++

也就是说：

BF 是主串也跟着折腾
KMP 是主串尽量别动，让模式串自己跳

题型5：手算 next 数组¶

原书试题里会出现：

给定一个模式串
让你求 next
有时位序从 1 开始
有时位序从 0 开始

这类题最容易错的不是不会算，而是：

没先看清编号方式
把 PM 表和 next 数组直接混用了

建议固定流程：

先算每个前缀的最长相等前后缀长度
再根据题目定义转成 next
最后核对第一个元素到底该写 0 还是 -1

题型6：手算 nextval 数组¶

这类题比 next 更容易错，因为你要多判断一步：

若当前字符和即将跳去的位置字符不同，直接记原跳转
若相同，就继续递归压缩

理解关键：

nextval 的目标不是“和 next 不一样”
而是“避免跳到一个必然还会失配的位置”

题型7：比较次数题¶

原书里有多道题都在考：

给主串和模式串
问 KMP 匹配成功前一共比较了多少次

做这类题不要光看公式，要老老实实模拟。

固定方法：

先写出 next 或 nextval
再按 i、j 的变化一轮轮模拟
每发生一次字符比较，就加 1

不要偷懒，因为这类题最容易在“失配后到底比了几次”这里少算或多算。

题型8：滑动距离题¶

这类题常结合 nextval 来出。

当模式串第 j 个字符失配时，常问：

模式串最多向右滑动多少位？

抓法是：

先看题目是 0-based 还是 1-based
再根据题目定义算 j - next[j] 或 j - nextval[j]

这里千万别把不同教材里的定义混在一起。

19.2 选择题级别的结论清单¶

下面这些结论建议你直接背熟：

模式匹配是在主串中找与模式串相同的子串
KMP 匹配时主串指针不回退
BF 最坏复杂度是 O(nm)
KMP 复杂度是 O(n + m)
KMP 失配时通常 i 不变、j = next[j]
next 是否整体右移、首元素是否取 0 或 -1，必须看题目定义
nextval 的作用是减少无意义比较

19.3 综合应用题整理¶

综合题1：为什么 `next[1] = 0`¶

这是原书特别典型的一道解释题。

答案核心是：

当模式串第一个字符就和主串当前字符失配时
模式串内部已经没有更短的前后缀可复用
只能让主串后移一位，再重新从模式串开头开始

所以教材常把：

next[1] = 0

理解成一种“无法再往内部跳”的标记。

综合题2：为什么定义里要取最大的 k¶

这题本质是在问：

为什么要找最长相等前后缀？

原因是：

失配后，希望模式串右滑距离尽可能小
这样才不会漏掉潜在匹配
而“最长相等前后缀”正对应“最远还能复用多少已匹配信息”

换句话说：

取最大的 k
就是在保证不漏匹配的前提下，尽量少丢信息

综合题3：为什么有些情况 next 只能取 1 或 0¶

当失配后：

不存在任何非空的相等前后缀
那就只能让模式串从开头重新尝试

在不同编号体系下，结果会写成：

1
或 0
或 -1

所以这题真正考的是：

你有没有分清“逻辑含义”和“具体编码方式”

19.4 原书综合题：`P = "aabaac"` 的 next 数组¶

这是非常适合练手的一题。

模式串：

P = "aabaac"

按原书常见的 1-based 写法，可得到：

next = [0, 1, 2, 1, 2, 3]

你可以这样理解：

第 1 位失配时，无路可退，所以为 0
第 2 位前面只有一个 a，所以下一次从第 1 位比较
到后面逐步利用前缀 a、aa 的重合结构
最终形成 0, 1, 2, 1, 2, 3

这一题的价值不是结果本身，而是让你体会：

next 不是瞎填出来的
它完全由模式串的自重复结构决定

19.5 原书综合题：`S = "aabaabaabaac"` 与 `P = "aabaac"` 的 KMP 过程¶

这是把 next 和匹配过程连起来的一道典型题。

主串：

S = "aabaabaabaac"

模式串：

P = "aabaac"

前面已经求得：

next = [0, 1, 2, 1, 2, 3]

做题时你应该抓住的不是每一步字符，而是下面这条主线：

第一趟从头开始比较
某一位失配后，主串不回退
模式串根据 next 跳到较短但仍可能成功的位置
继续比较
最终在后面位置完成完整匹配

这一题最值得你学到的是：

KMP 不是“神秘跳转”
而是“拿模式串已经暴露出来的结构信息继续用”

19.6 这一组试题最容易错在哪里¶

错点1：把位序体系搞混¶

这是第一大坑。

同样一道题：

若从 1 开始编号
若从 0 开始编号

得到的 next 写法可能完全不同。

所以你下笔前第一件事永远是：

先确认编号方式

错点2：把 PM 表直接当 next¶

这也是高频错误。

很多同学会：

先求出最长相等前后缀长度
结果直接抄成 next

但实际上：

PM 表是一个中间工具
next 还要看题目采用的定义方式再转一次

错点3：比较次数题只看结果不模拟¶

比较次数题不能只凭感觉。

因为：

每次失配后到底是立即回跳
还是先经历一次 j == 0
或者是否用的是 nextval

都会影响总次数。

错点4：以为 KMP 就一定远快于 BF¶

理论上 KMP 更优，但原书也提醒了一点：

很多普通场景下，BF 实际表现未必很差
KMP 真正明显占优时，往往是模式串有较多局部重复结构的时候

这点你要会辨别。

20. 这一部分怎么刷最有效¶

建议按下面的路线完成第 4 章刷题训练：

先背结论清单
再手算两个 next 数组
再手推一遍 KMP 匹配过程
再去做比较次数题
最后再做 nextval 和滑动距离题

顺序别反。

因为：

连 next 都不稳时去做比较次数题，很容易乱
连 KMP 主串不回退都没吃透时去做 nextval，会更乱

你可以把这一章的刷题升级路线理解成：

先会概念
再会手算
再会模拟
最后会分析效率和变种

做到这里，第 4 章基本就不是“看过”，而是真的进入“会做题”的状态了。

21. 题型索引¶

为方便后续复习和查漏，第 4 章常见题型按“知识点 -> 题目表现”重新归类如下。

21.1 概念识别类¶

这类题通常不难，但很容易因为概念混淆丢分。

常见问法：

什么是串、子串、主串
空串和空格串的区别
串和线性表的联系与区别
模式匹配与求子串的区别

这类题对应优先回看：

本书第4章正文 的 4.1 串的定义和实现
本书第4章正文 的 4.4 串的基本操作

21.2 存储结构类¶

这类题围绕“串在内存里怎么放”来考。

常见问法：

定长顺序存储的特点
堆分配存储的特点
两种存储方式的区别
为什么动态分配能避免定长截断问题

这类题对应优先回看：

本书第4章正文 的 4.5 串的存储结构
第4章普通代码版 的 SString、HString 定义

21.3 基本操作实现类¶

这类题考你有没有把“抽象串操作”翻译成真实代码。

常见问法：

赋值
判空
比较
求长
取子串
串连接

这类题对应优先回看：

第4章普通代码版
第4章逐行注释版代码

21.4 BF 朴素匹配类¶

这类题主要考：

BF 的流程
为什么会回溯
为什么最坏复杂度是 O(nm)
失配后主串起点怎么更新

这类题对应优先回看：

本书第4章正文 的 5.2 朴素模式匹配 BF 的思想
第4章普通代码版 的 IndexBF

21.5 PM / next 手算类¶

这是第 4 章的核心题型之一。

常见问法：

求模式串的部分匹配值表
根据定义求 next
解释 next[1] = 0
为什么取最大的 k

这类题对应优先回看：

本书第4章正文 的 6.2 前缀、后缀、部分匹配值 PM
本书第4章正文 的 13. 逐行拆解：GetNextArray
本书第4章正文 的 19. 原书试题区整理版

21.6 KMP 匹配过程类¶

这类题主要考你是否真懂：

失配时为什么 i 不回退
j 为什么要跳到 next[j]
匹配成功时如何返回位置
如何一轮轮模拟 KMP

这类题对应优先回看：

本书第4章正文 的 14. 逐行拆解：IndexKMP
第4章普通代码版 的 IndexKMP

21.7 nextval / 优化类¶

这类题通常更进一步，问：

nextval 为什么比 next 更优
什么叫“无意义比较”
失配时模式串最多右滑多少位

这类题对应优先回看：

本书第4章正文 的 6.8 nextval 为什么还要再优化一次
第4章普通代码版 的 GetNextValArray

21.8 比较次数与综合分析类¶

这类题是最容易“看懂但做错”的。

常见问法：

到匹配成功为止，一共比较了多少次
用 next 和 nextval 时比较次数差多少
某次失配后下一步 i、j 分别是多少

这类题对应优先回看：

本书第4章正文 的 19. 原书试题区整理版
本书第4章正文 的 16. 手推 KMP 时的固定步骤

22. 刷题路径¶

第 4 章不适合乱刷，最好按梯度推进。

22.1 基础训练：概念打底¶

目标：

不再混淆空串、空格串、子串、主串
搞清楚模式匹配到底在做什么
知道顺序存储和堆存储的区别

这一部分不要急着碰 KMP 细节。

22.2 进阶训练：朴素匹配打底¶

目标：

能手推 BF
知道为什么主串会回溯
能解释 O(nm) 的来源

如果这一部分没稳，后面学 KMP 会像在空中建楼。

22.3 强化训练：专攻 PM 和 next¶

目标：

会列前缀和后缀
会求最长相等前后缀长度
会由定义或 PM 表推 next

这是整章最核心的一轮。

因为很多人不是死在 KMP 主循环，而是死在：

根本不会求 next

22.4 第四轮：专攻 KMP 过程模拟¶

目标：

会模拟 i、j 的变化
失配时知道该怎么跳
明白“主串不回退”到底体现在哪里

建议这轮配合：

本书第4章正文
第4章逐行注释版代码

一起看。

22.5 第五轮：做 nextval 和比较次数题¶

目标：

会区分 next 和 nextval
会做滑动距离题
会做字符比较次数题

这轮才算真正把第 4 章“拔高”。

23. 自学检查清单¶

如需判断自己第 4 章到底学到什么程度，可对照下面这份清单。

23.1 概念层检查¶

你应该能独立说清：

什么是串
什么是子串
什么是主串
空串和空格串有什么区别
串和线性表的操作重点为什么不同

23.2 存储层检查¶

你应该能解释：

SString 里字符和长度分别存在哪里
HString 为什么需要 malloc 和 free
为什么定长顺序串会遇到截断问题

23.3 算法层检查¶

你应该能不用看答案直接说出：

BF 为什么慢
KMP 为什么快
KMP 的关键不是“模式串移动了”，而是“主串不回退”
next 的作用是什么
nextval 又比 next 多优化了什么

23.4 手算层检查¶

你应该能做到：

给一个模式串，手写它的 PM 表
给一个模式串，手写它的 next
给一个模式串，手写它的 nextval
模拟一轮 KMP，写出 i、j 如何变化

23.5 代码层检查¶

你应该至少能自己读懂：

第4章普通代码版 里的 IndexBF
第4章普通代码版 里的 GetNextArray
第4章普通代码版 里的 IndexKMP
第4章普通代码版 里的 GetNextValArray

如果觉得普通版还吃力，就应该能借助：

第4章逐行注释版代码

把核心函数顺着读下来。

23.6 刷题层检查¶

你应该能比较稳地做：

概念选择题
复杂度题
next / nextval 手算题
KMP 过程题
比较次数题

如果这些都可以，那第 4 章基本就已经过关了。

25. 原书试题逐题详细解答版¶

这一节把原书试题区进一步展开成“题目本质 + 详细思路 + 易错提醒”的形式。
重点不是死记答案字母，而是把每道题背后的判定逻辑吃透。

25.1 单项选择题¶

第 1 题¶

题目本质：

问“在一个串里找另一个串第一次出现的位置”这个操作叫什么。

正确答案：

C. 模式匹配

详细思路：

求子串是“从一个已知串中截出一段连续部分”。
判断相等是“比较两个串是否完全一致”。
连接是“把两个串首尾拼起来”。
模式匹配是“在主串中寻找与模式串相同的子串”。

所以题目描述的正是模式匹配。

易错提醒：

“求子串”是截取，不是查找。

第 2 题¶

题目本质：

问 KMP 匹配时，主串指针有什么性质。

正确答案：

B. 不会变小

详细思路：

BF 失配时，主串起点可能回到前面，再重新比较。
KMP 失配时，主串当前位置尽量保留，主要回跳的是模式串指针。
所以主串指针不会回退，也就是不会变小。

易错提醒：

别把“不会回退”误写成“不会变大”，主串指针当然会向前走。

第 3 题¶

题目本质：

问朴素匹配和 KMP 的理论时间复杂度。

正确结论：

BF 最坏时间复杂度：O(nm)
KMP 时间复杂度：O(n + m)

详细思路：

朴素匹配最坏时会进行 n - m + 1 趟尝试。
每趟最多比较 m 次。
所以最坏复杂度是 O(nm)。
KMP 中主串指针基本只向前走，模式串指针虽会回跳，但总回跳次数受控。
因此总复杂度是 O(n + m)。

易错提醒：

实际场景下 BF 有时也不慢，但题目问“理论最坏复杂度”时必须写 O(nm)。

第 4 题¶

题目本质：

问 KMP 匹配时，若当前字符失配，主串指针 i 怎么变。

正确结论：

i 不变

详细思路：

KMP 的核心是：主串不回退。
失配时，通过 next[j] 让模式串跳到更合适的位置。
于是当前主串字符还要继续参与比较，所以 i 保持不变。

易错提醒：

很多同学会把 BF 的习惯带进来，以为失配就要改 i。

第 5 题¶

题目本质：

仍然在考 KMP 中主串指针是否回溯。

正确答案：

结合原书答案区，这题应选“主串指针不回溯”的选项。

详细思路：

这一题和第 2 题本质相同，只是换了问法。
判断标准不变：

主串不回退
主要变化的是模式串指针

易错提醒：

不要被题目换说法绕进去，核心仍然是“主串不回溯”。

第 6 题¶

题目本质：

给模式串 ababaaababaa
要求求出一种定义下的 next 数组

正确答案：

按原书答案，应选 C

对应 1-based 风格结果可整理为：

next = [0, 1, 1, 2, 3, 4, 2, 2, 3, 4, 5, 6]

详细思路：

先求这个串每个前缀的最长相等前后缀长度，也就是 PM 值。
再将 PM 表整体右移一位。
若题目采用原书这套 next[1] = 0 的定义，则再整体加 1。

为什么能这么做：

在 1-based 体系下，原书给出的关系是：
next[j] = PM[j - 1] + 1
因此只要 PM 表没算错，next 就能顺势得到。

易错提醒：

最大坑不是不会算，而是没看清题目采用的到底是哪套 next 定义。

第 7 题¶

题目本质：

还是模式串 ababaaababaa
但换成另一种定义方式求 next

正确答案：

按原书答案，应选 C

一种常见的 0-based / 首元素为 -1 写法可以整理为：

next = [-1, 0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5]

详细思路：

第 6 题和第 7 题考的不是两个不同串。
它们考的是同一个模式串在不同 next 定义下的表示。
所以只要你知道题目下标从 0 还是 1 开始，很多混乱就会消失。

易错提醒：

千万不要把第 6 题算出的结果原样搬到第 7 题。

第 8 题¶

题目本质：

主串 S = "aabaaaba"
模式串 T = "aaab"
用 KMP 匹配，问到匹配成功为止，一共比较了多少次字符

正确答案：

按原书答案，应选 B

总比较次数：

详细思路：

原书整理出的分段比较过程可以概括为：

第一趟连续比较 3 次后失配
第二趟比较 1 次
第三趟比较 1 次
第四趟比较 4 次并成功

所以总次数为：

3 + 1 + 1 + 4 = 9

为什么这里容易出错：

很多人只看“成功时比了几次”
但忽略了中间几次失配后的继续比较

易错提醒：

比较次数题一定要一轮轮模拟，不能只凭感觉估。

第 9 题¶

题目本质：

还是上题的主串和模式串
但改成使用改进后的 KMP，也就是 nextval

正确答案：

按原书答案，应选 C

总比较次数：

详细思路：

原书给出的主线是：

第一趟比较 3 次后失配
因为 nextval 跳得更合理，后面少了无意义比较
第二趟比较 4 次后成功

所以总次数为：

3 + 4 = 7

为什么比第 8 题少：

nextval 避免了跳到一个“字符相同但必然还会失配”的位置
因而删掉了一些白比的比较

易错提醒：

nextval 的核心价值不是“写法不同”，而是“减少无意义比较”。

第 10 题¶

题目本质：

已知模式串 s = "ababaaa"
使用 nextval
问与第 6 个字符失配时，模式串向右滑动的距离

正确答案：

按原书答案，应选 B

滑动距离：

详细思路：

原书说明采用 0-based 编号。
当比较到 s[j] 失配时，滑动距离为：

j - nextval[j]

此题在对应位置有：

j = 5
nextval[j] = 3

因此：

5 - 3 = 2

易错提醒：

先看题目编号从 0 开始还是从 1 开始，不然公式会错一位。

第 11 题¶

题目本质：

已知主串与模式串
在第一次出现失配时，给出 i = j = 5
问下次开始比较时 i、j 分别是多少

正确答案：

按原书答案，应选 C

即：

i = 5, j = 2

详细思路：

题目是 0-based 编号。
失配时 i 不回退。
要根据模式串的 next 数组，让 j 跳到 next[j]。
原书计算后得到对应跳转位置为 2。

所以：

i 仍是 5
j 变成 2

易错提醒：

这题最大的坑是看见“下次开始匹配”就下意识把 i 也往后改。

第 12 题¶

题目本质：

主串 T = "abaabaabcabaabc"
模式串 S = "abaabc"
采用 KMP 匹配
问到匹配成功为止，字符比较次数是多少

正确答案：

按原书答案，应选 B

总比较次数：

详细思路：

原书给出的比较过程可压缩为：

第一趟连续比较 6 次，在模式串第 5 位失配
然后根据 next[5] 跳转
第二趟又比较 4 次，完成匹配

所以总次数：

6 + 4 = 10

易错提醒：

比较次数题不要只看“跳了几次”，而要看“真正做了几次字符比较”。

第 13 题¶

题目本质：

使用修正后的 next 数组，也就是 nextval
模式串 s = "aabaab"
问失配时模式串向右滑动的最长距离

正确答案：

按原书答案，应选 A

最长滑动距离：

详细思路：

原书按 0-based 编号处理。
当比较到 s[j] 失配时，右滑距离是：

j - nextval[j]

对各位置计算后可发现：

在 j = 4 时
滑动距离最大
最大值为 5

易错提醒：

这类题本质上是在考你会不会从 nextval 反推出“可跳过多少无用比较”。

25.2 综合应用题¶

综合题 1¶

题目核心：

已知 next[j] 的定义，说明：

为什么 next[1] = 0
为什么要取最大的 k
“其他情况”是什么，为什么取相应初值

详细解答：

1. 为什么 `next[1] = 0`¶

当模式串的第 1 个字符和主串当前字符失配时：

模式串内部没有更短的前后缀可复用
说明无法在模式串内部继续跳
只能把主串位置后移一位，再从模式串开头重新比

所以教材常把它记作：

next[1] = 0

它表达的是：

“模式串已经退无可退”

2. 为什么要取最大的 `k`¶

设主串第 i 位和模式串第 j 位失配。
我们想找一个新的位置 k，让模式串第 k 位继续和主串第 i 位比较。

这个 k 必须满足：

前面的那一段已经匹配过的信息还能继续复用
同时不能漏掉可能的匹配

为什么取最大的 k：

因为 j - k 表示模式串向右滑动的距离
取最大的 k，等价于让右滑距离尽量小
这样保留的信息最多，也最不容易漏掉潜在匹配

k 最大能到多少：

j - 1

因为它必须严格小于 j。

3. “其他情况”是什么¶

所谓“其他情况”，本质上是指：

不存在满足条件的非空相等前后缀
也就是说，没有任何可复用的结构信息

这时就只能退回到模式串开头重新比。
在不同教材体系下，这个值可能记成：

1
或 0
或 -1

所以真正该掌握的不是死记某个数字，而是：

它表示“只能从头再试”

易错提醒：

这题最容易错在把“定义含义”和“下标表示方式”混为一谈。

综合题 2¶

题目核心：

求模式串 P = "aabaac" 的 next 数组
再模拟主串 S = "aabaabaabaac" 与模式串 P = "aabaac" 的 KMP 过程

第一问：求 `next`¶

原书采用的 1-based 风格结果为：

next = [0, 1, 2, 1, 2, 3]

详细推导如下。

第 1 位¶

next[1] = 0

因为第一个字符失配时无路可退。

第 2 位¶

题目约定下：

next[2] = 1

表示从模式串第 1 位重新比较。

第 3 位¶

此时考察前缀结构：

已有可复用长度来自前面一个 a
当前又能继续衔接

所以：

next[3] = 2

第 4 位¶

此时会遇到字符不相等：

先尝试用更长的前后缀复用
失败后再沿 next 往前跳
最终只能回到较短位置

所以：

next[4] = 1

第 5 位¶

当前位置重新形成可复用结构，因此：

next[5] = 2

第 6 位¶

继续扩展已有的相等前后缀，因此：

next[6] = 3

最终得到：

next = [0, 1, 2, 1, 2, 3]

第二问：模拟 KMP 匹配过程¶

主串：

S = "aabaabaabaac"

模式串：

P = "aabaac"

先记住已经求出的：

next = [0, 1, 2, 1, 2, 3]

第一趟¶

从主串和模式串的第 1 位开始比
前面一段能够顺利匹配
到后面某位出现失配
此时主串不回退，模式串按 next 跳

原书给出的关键状态是：

第一趟失配时：i = 6, j = 6

第二趟¶

因为：

next[6] = 3

所以模式串不是回到开头，而是让第 3 位继续和当前主串字符比较。
这一步正体现了 KMP 的价值：

主串不回退
模式串保留前面可复用的结构信息

原书给出的关键状态是：

第二趟失配时：i = 9, j = 6

第三趟¶

模式串继续依据 next 跳转，再往后比较，最终完成匹配成功。

你真正要抓住的是主线：

失配后主串不退
模式串不盲目回到开头
而是利用已知前后缀结构继续比

这就是 KMP 的本质。

易错提醒：

这题如果只会背结果，不会解释“为什么从第 3 位继续”，那就说明 next 还没真正理解。

25.3 这一组题做完后你应该掌握什么¶

如果你把这一组题真的做透了，说明你至少已经掌握了：

什么叫模式匹配
为什么 KMP 的主串不回退
BF 和 KMP 的复杂度差异
PM、next、nextval 的关系
比较次数题的模拟方法
滑动距离题的判定方式
如何把“手算 next”和“实际 KMP 匹配过程”连起来

这几项一旦都稳了，第 4 章就真的不只是“看过”，而是已经进入“能考试、能讲给别人听、能写成代码”的阶段了。

站内代码入口¶

对应代码专题：第4章串代码
如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

继续阅读¶

← 上一章：第3章栈、队列和数组下一章：第5章树与二叉树 →

第4章 串（自学增强版）¶

1. 本章定位¶

2. 学习目标¶

3. 本章结构总览¶

4. 4.1 串的定义和实现¶

4.1 串的定义¶

4.2 必须分清的几个概念¶

4.2.1 串长¶

4.2.2 空串 vs 空格串¶

4.2.3 子串与主串¶

4.2.4 位置¶

4.3 串和线性表有什么关系¶

4.4 串的基本操作¶

4.5 串的存储结构¶

4.5.1 定长顺序存储¶

4.5.2 堆分配存储¶

4.5.3 块链存储¶

4.6 真实代码：串的基本操作¶

4.7 伪代码与真实代码对照：取子串¶

原书思路版伪代码¶

对应真实代码¶

理解重点¶

5. 4.2 串的模式匹配¶

5.1 模式匹配到底在做什么¶

5.2 朴素模式匹配 BF 的思想¶

原书思路版伪代码¶

对应真实代码¶

为什么 i = i - j + 2¶

5.3 BF 为什么慢¶

6. KMP：真正的重点¶

6.1 KMP 在解决什么问题¶

6.2 前缀、后缀、部分匹配值 PM¶

前缀¶

后缀¶

部分匹配值 PM¶

6.3 KMP 的直觉版解释¶

6.4 next 数组是什么¶

6.5 PM 表与 next 数组的关系¶

6.6 原书伪代码与真实代码对照：求 next 数组¶

原书思路版伪代码¶

对应真实代码¶

理解重点¶

6.7 KMP 匹配伪代码与真实代码¶

原书思路版伪代码¶

对应真实代码¶

关键观察¶

6.8 nextval 为什么还要再优化一次¶

对应真实代码¶

7. 真实代码运行结果与知识点对应¶

8. 高频易错点¶

8.1 空串不等于空格串¶

8.2 子串必须连续¶

8.3 教材位序和代码下标混淆¶

8.4 KMP 的关键不是“模式串滑动很聪明”¶

8.5 next 和 nextval 不要混记¶

9. 刷题与自学建议¶

10. 本章小结¶

11. 当前版本完成度¶

12. 代码阅读入口¶

13. 逐行拆解：GetNextArray¶

13.1 先说整体任务¶

13.2 逐行理解¶

13.3 这一段最容易卡住的点¶

为什么 j = next[j] 不会乱掉¶

为什么 j == 0 时要特殊处理¶

13.4 一句话记忆¶

14. 逐行拆解：IndexKMP¶

14.1 先说整体任务¶

14.2 逐行理解¶

14.3 这里最容易误解的点¶

为什么失配时 i 不动¶

为什么 j 会突然跳很远¶

14.4 一句话记忆¶

15. 把 GetNextArray 和 IndexKMP 连起来看¶

16. 手推 KMP 时的固定步骤¶

19. 原书试题区整理版¶

19.1 单项选择题高频考点整理¶

题型1：什么叫模式匹配¶

题型2：KMP 中主串指针的性质¶

题型3：BF 和 KMP 的时间复杂度¶

第4章串（自学增强版）¶

为什么 `i = i - j + 2`¶

为什么 `j = next[j]` 不会乱掉¶

为什么 `j == 0` 时要特殊处理¶

为什么失配时 `i` 不动¶

为什么 `j` 会突然跳很远¶

综合题1：为什么 `next[1] = 0`¶

19.4 原书综合题：`P = "aabaac"` 的 next 数组¶

19.5 原书综合题：`S = "aabaabaabaac"` 与 `P = "aabaac"` 的 KMP 过程¶

1. 为什么 `next[1] = 0`¶

2. 为什么要取最大的 `k`¶

第一问：求 `next`¶