数据结构第 4 章：串

本章参考本站的 408 真题 → 408 模拟题 → Algorithm 字符串专题 进行整理。

资料说明：本站中，408 真题的数据结构目录目前只有“绪论、线性表、栈/队列/数组、树、图、查找、排序”，没有单列“串”这一章；而 408 模拟题中明确有“第 4 章 串”，目前收录的 5 道题全部集中在 KMP、next 和 nextval。所以这一章无法像树、图那样列出大量统考真题，下文将把“网站实际收录的模拟题”和“Algorithm 中的补充题”明确区分。(docs.any1.tech)

检查发现，网站本章有一道题的答案存在明显计数矛盾，文中会单独指出。

一、第 4 章到底要学什么？

如果按照考研复习价值排序，建议把这一章分成四层：

本站的模拟题几乎全部落在第三、第四层。(Any Docs)

因此：

这一章真正的核心不是“字符串操作”，而是 KMP。

二、先把串的基本概念弄清楚

1. 什么叫串？

串就是由有限个字符组成的有限序列。

例如

长度为

空串的长度为 $0$。

要特别区分：

• 空串：没有字符；
• 空格串：里面有空格字符，长度不一定为 $0$。

三、子串、前缀、后缀

这几个概念是 KMP 的地基。

假设

1. 子串

连续的一段字符才叫子串。

例如：

• "aba" 是子串；
• "aaa" 不是这个串的连续子串。

2. 前缀

从第一个字符开始，但不能取整个串。

ababa 的真前缀：

3. 后缀

必须到最后一个字符结束，但不能取整个串。

其真后缀：

所以最长相等真前缀、真后缀是

长度为

本站 Algorithm 的 KMP 资料也是从这个定义建立前缀表：前缀不能包含最后一个字符，后缀不能包含第一个字符。(Any Docs)

四、第一类题：朴素模式匹配 BF

虽然网站本章模拟题没有专门出 BF，但为了理解 KMP，必须先知道 KMP 到底优化了什么。

设：

主串：

模式串：

目标：找出 $P$ 是否出现在 $S$ 中。

BF 的思想

从主串某一位置开始，一个字符一个字符比较。

失败以后：

主串候选起点向右移动一位，模式串重新从头比较。

例如已经匹配：

S: a b a b a b c
P: a b a b c
        ↑最后失配

普通 BF 会把模式串整体向后移动，再从

P[0]

开始。

问题就在这里：

前面已经比较成功的大量信息全部浪费了。

五、BF 的复杂度

设主串长度为 $n$，模式串长度为 $m$。

最坏情况下，每一个候选位置都比较接近 $m$ 次。

因此：

更具体一些，候选起点最多有

个，因此最坏比较量级约为

六、KMP 到底解决了什么？

本站 Algorithm 的 KMP 页面给出的核心思想非常准确：

失配以后，不必忘掉此前已经匹配的字符，可以利用模式串自身的前后缀结构继续匹配。(Any Docs)

KMP 最重要的一句话是：

主串指针原则上不回退，回退的是模式串指针。

这句话几乎可以直接解决网站中的第一道模拟题。

七、为什么前后缀能够发挥作用？

来看一个经典情况。

已经匹配了：

主串: ... a b a b a X
模式:     a b a b a Y

前五个字符

ababa

已经成功。

然后

观察 ababa：

最长相等前后缀是

aba

那么主串中刚刚匹配成功的最后三个字符已经知道是：

aba

而模式串开头三个字符也是：

aba

因此根本没有必要重新比较它们。

直接把模式串调整到：

      a b a b a Y
          a b a b a Y

继续即可。

八、整个 KMP 的灵魂：最长相等前后缀

现在定义一个最清楚、最不容易混淆的数组：

表示：

模式串 $P[0\dots i]$ 的最长相等真前缀与真后缀长度。

例如：

逐位计算：

所以：

九、为什么失配以后要看前一个位置？

假设模式串位置 $j$ 发生失配。

也就是说：

已经全部匹配成功。

那么应该研究的是：

的最长相等前后缀。

因此使用现代前缀函数写法：

这就是 KMP 最关键的跳转。

十、这一章最大的坑：next 数组不止一种定义

这一点非常重要。

本站里的几道题实际上使用了不同的下标体系和不同版本的 next 定义。如果只背数组，很容易出现以下问题：

同一个模式串，为什么不同书的 next 不一样？

原因不是谁一定错了，而是定义不同。

十一、最推荐掌握的三套表示

第一套：现代前缀函数 $\pi$

0 开始编号。

例如：

P = a b a b a
    0 1 2 3 4

有：

失配：

这是理解原理时最推荐使用的形式。

十二、第二套：王道常见 1 下标 next

本站的 王道·卷七-Q04 就采用这种形式。

其特点：

通常：

如果在模式串第 $j$ 位失配：

十三、网站题 1：失配后到底和哪一个字符比较？

题目来源：王道·卷六-Q04

题目大意：

使用 KMP 时，主串在位置 $i$ 与模式串位置 $j$ 发生失配。已知

$$k=next[j]$$

问下一轮应该让模式串哪个位置与主串当前位置 $i$ 对齐？ (Any Docs)

答案：

为什么？

KMP 失配时：

不回退。

而：

因此：

于是下一次比较：

所以选 $k$。

这一题真正考什么？

不是考计算。

它在考一句话：

KMP 失配：主串不回退，模式串根据 next[j] 回退。

常见干扰项

题目还给出了类似

这样的东西。

这是经典陷阱。

next 是：

根据模式串自身结构计算的。

所以它和主串当前位置 $i$ 没有这种意义上的关系。

十四、第三套：0 下标、-1 哨兵版 next

另一套常见形式：

P[0],P[1],...

并规定

例如：

ababac

网站给出的普通 next 为：

(Any Docs)

这种情况下失配时仍然写：

如果：

则：

十五、考试时如何避免 next 定义混乱？

看到题以后不要马上算。

第一步先观察：

情况 A

如果：

基本是 1 下标版本。

情况 B

如果：

基本是 0 下标哨兵版本。

情况 C

如果第一个值为

而且每项直接表示最长相等前后缀长度，则可能实际上是在使用前缀函数 / LPS。

十六、网站题 2：手算 next 数组

题目来源：王道·卷七-Q04

题目：

模式串为

acaba

求采用题目约定时的 next 数组。(Any Docs)

网站答案：

即

十七、这道题怎样快速手算？

使用 1 下标：

位置:  1 2 3 4 5
字符:  a c a b a

第 1 位

约定：

第 2 位

题目这一套定义规定：

第 3 位

计算第 3 位失配以后应该去哪里。

研究当前位置之前：

ac

ac 没有非空相等真前后缀。

所以：

第 4 位

研究：

aca

最长相等前后缀：

a

长度为

下一次应该比较模式串第

位，因此：

第 5 位

研究：

acab

没有非空相等前后缀。

所以：

最终：

网站给出的结果也是这一数组。(Any Docs)

十八、最通用的 next 手算方法

不要背递推式，考选择题最好直接这么做：

如果问

就看：

找最长相等真前后缀。

设长度为 $L$。

那么王道这一套 1 下标写法中：

特殊：

十九、例：自己练一个

求模式串

ababaca

的 1 下标 next。

依次：

$next[1]$

$next[2]$

看 a：

$next[3]$

看 ab：

没有相等前后缀：

$next[4]$

看 aba：

最长：

a

所以：

$next[5]$

看 abab：

最长：

ab

所以：

$next[6]$

看 ababa：

最长：

aba

所以：

$next[7]$

看 ababac：

无：

因此：

二十、KMP 为什么是线性的？

设：

主串长度：

模式串长度：

构造前缀表需要：

匹配过程：

所以总时间：

相比 BF：

这就是 KMP 的核心优势。本站 Algorithm 的 strStr() 页面也明确给出了 KMP 总复杂度

而暴力匹配为

。(Any Docs)

二十一、如何在线性时间构造前缀表？

对于模式串：

定义：

令：

当：

不断：

直到：

• 找到相等；
• 或 $j=0$。

如果：

则：

最后：

模板

vector<int> prefixFunction(const string& p) {
    int m = p.size();
    vector<int> pi(m, 0);

    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];

        while (j > 0 && p[i] != p[j]) {
            j = pi[j - 1];
        }

        if (p[i] == p[j]) {
            ++j;
        }

        pi[i] = j;
    }

    return pi;
}

二十二、KMP 匹配模板

int KMP(const string& s, const string& p) {
    if (p.empty()) return 0;

    vector<int> pi = prefixFunction(p);

    int j = 0;

    for (int i = 0; i < (int)s.size(); ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = pi[j - 1];
        }

        if (s[i] == p[j]) {
            ++j;
        }

        if (j == (int)p.size()) {
            return i - p.size() + 1;
        }
    }

    return -1;
}

不用死背代码，但一定要理解这一句：

二十三、为什么 next 还能继续回退？

这也是很容易出选择题的地方。

假设已匹配串为：

abababa

最长相等前后缀可能是：

ababa

如果接下来仍然失配，并不意味着必须回到 0。

因为：

ababa

本身也有自己的最长相等前后缀：

aba

所以可以继续：

本质就是：

border 的 border 仍然可能是 border。

因此 KMP 的回退形成一条链。

二十四、nextval 为什么出现？

普通 next 虽然已经避免了主串回退，但还有可能产生：

明知道一定失败，却还再比较一次。

例如模式串：

aaaab

如果当前主串字符已经和一个 a 失配，而普通 next 又让模式串退到另一个字符也是 a 的位置：

主串字符 X ≠ a

下一次仍比较：

显然：

已经知道了。

这就是无效比较。

二十五、nextval 的核心思想

如果普通回退位置字符和当前失配字符相同：

那么回退到 next[j] 没意义。

应该继续跳：

否则：

即：

二十六、网站题 3：nextval 后下一次从哪里比较？

来源：王道·卷八-Q04

题目给出：

主串

aabaabcabc

模式串

aaabc

采用 nextval 优化的 KMP。

在

时发生失配，问下一次真正比较时的 $i,j$。(Any Docs)

网站答案：

二十七、为什么不是 $i=2,j=-1$？

采用这一题的 0 下标哨兵写法：

因此失配后首先：

此时：

暂时没有改变。

所以中间状态是：

但是 KMP 主循环遇到

以后会执行：

于是：

所以：

**“失配后的瞬间状态”和“下一次真正字符比较的状态”**一定要区分。

网站此题正是在考这一点。(Any Docs)

二十八、这是考试中非常阴险的一种设问

如果问：

“失配以后指针如何变化？”

可能回答：

此时 $i$ 暂时不变。

但如果问：

“下一次开始字符比较时？”

那么当

时，还必须再执行：

因此答案可能完全不同。

二十九、网站题 4：综合判断题

来源：竟成·模拟一-08

模式串：

ababac

主串：

cbabababac

考查内容包括：

1. 第一次失配以后 $i,j$ 怎么走；
2. 普通 next；
3. nextval；
4. 某次失配后的状态；
5. 总比较次数。(Any Docs)

网站最终选：

即总比较次数为：

三十、先求普通 next

0 下标、$-1$ 哨兵版：

P = a b a b a c
    0 1 2 3 4 5

普通：

三十一、再求 nextval

依次判断：

$j=0$

$j=1$

b != a

所以：

$j=2$

当前位置：

a

回退位置也是：

a

如果退过去，必然再次失配。

所以继续跳：

类似地：

最后：

所以：

网站给出的也是这一结果。(Any Docs)

三十二、把整段匹配真正跑一遍

主串：

c b a b a b a b a c
0 1 2 3 4 5 6 7 8 9

模式：

a b a b a c
0 1 2 3 4 5

比较 1

失配。

累计：

比较 2

下一个真正字符比较：

失配。

累计：

接下来 5 个字符连续成功

从：

开始：

a b a b a

与：

a b a b a

匹配。

增加：

累计：

下一次

而：

失配。

累计：

此时：

注意：

不回退。

继续比较

现在：

成功。

累计：

再比较：

累计：

最后：

累计：

成功。

所以：

三十三、这类“比较次数题”怎么做最快？

不要靠感觉。

画一个状态表：

最稳。

三十四、这里还有一个非常值得注意的题目表述问题

网站解析认为该题选项 A 不正确，因为：

首字符失配后虽然可以先令 $j=-1$，但下一次真正比较前还会执行 $i++,j++$。(Any Docs)

但严格从程序的单步状态变化看，如果选项只是说：

失配以后执行 $j=next[j]$，此时 $i$ 不动，

那么这种描述其实可以成立。

因此这种题最关键不是死记答案，而是看题目问：

• “失配后立即”；
• 还是“下一次真正开始比较”。

这是很典型的模拟题表述歧义。

三十五、网站题 5：比较次数题——这里的解析疑似有错误

这一题非常值得讲。

来源：竟成·模拟六-03

主串：

abaacaadaafa

模式串：

aada

题目问采用 KMP + nextval 匹配成功时进行多少次比较。

网站给出的答案是：

并给出了 nextval 和匹配过程。(Any Docs)

但是：

按照网站自己描述的 nextval 跳转过程，实际字符比较次数是 10，不是 12。

三十六、实际运行一遍

主串：

a b a a c a a d a a f a

模式：

a a d a

从头开始。

第 1 次

a : a

成功。

第 2 次

b : a

失败。

使用优化回退以后跳过重复的 a。

第 3 次

主串第 3 个：

a : a

成功。

第 4 次

a : a

成功。

第 5 次

c : d

失败。

第 6 次

回退后：

c : a

失败。

随后继续向后。

最后完整匹配 aada

需要：

次字符比较。

因此总数：

即：

三十七、为什么网站会得到 12？

因为如果使用普通 KMP、没有充分利用 nextval 跳过重复字符，那么会产生额外比较。

例如第一次

b : a

失败后，还可能再拿：

b : a

进行无意义比较。

而在 c 的位置也会多一次。

于是：

所以：

更关键的是，网站自己的文字步骤实际上也只描述出了：

却在最后写成了 12。(Any Docs)

因此这一题建议在题库里标记一下：

竟成·模拟六-03：答案/解析疑似错误或“比较次数”口径未说明清楚。

这是本章阅读里一个比较明显的问题。

三十八、nextval 最容易出的三类题

总结网站 5 道题，基本就是下面三种。

类型 A：直接求 next / nextval

套路：

1. 先求普通 next；
2. 再检查：

3. 相同继续跳；
4. 不同保留普通 next。

三十九、类型 B：给出失配位置，问下一步 $i,j$

核心：

普通失配

主串：

通常不回退。

若退到哨兵

下一步：

四十、类型 C：统计比较次数

唯一可靠方法：

模拟 $i,j$ 状态。

不要通过：

• 主串长度；
• 失配次数；
• 位移次数

去猜。

四十一、Algorithm 补充题 1：实现 strStr()

本站 Algorithm 字符串专题还有一道非常经典的 KMP 应用题：

题目

给定：

haystack

和：

needle

找出 needle 在 haystack 中第一次出现的位置；不存在返回 $-1$。

例如：

haystack = "hello"
needle   = "ll"

答案：

(Any Docs)

这其实就是：

KMP 的标准算法题版本。

四十二、这种大题的通用解法

假设模式长度：

当：

说明完整匹配。

此时主串当前位置为：

那么起始位置：

这是非常容易单独出选择题的公式。

四十三、Algorithm 补充题 2：重复子字符串

网站还收录了：

判断一个非空字符串能不能由某个较短子串重复若干次组成。

例如：

abab

可以：

所以为真。

而：

aba

不能。

(Any Docs)

四十四、这和 KMP 有什么关系？

假设字符串长度为：

整个串的最长相等真前后缀长度为：

那么候选最小周期为：

如果：

那么字符串可以由长度 $p$ 的子串重复组成。

因此判定条件：

网站的重复子字符串页面也是利用最后一个前缀表元素得到这个结论。(Any Docs)

四十五、为什么最小周期是 $n-L$？

例如：

abcabcabc

长度：

最长相等前后缀：

abcabc

长度：

于是：

而真正基本重复块正是：

abc

所以：

四十六、可以预测的一种考法：求最小循环节

例如自拟一题：

字符串 abababab 的最长相等真前后缀长度为 6，问其最小周期长度。

直接：

又：

所以最小循环节：

ab

长度：

四十七、另一种可能考法：统计所有匹配，包括重叠

例如：

主串：

aaaaa

模式：

aaa

出现位置：

共有：

次。

如果第一次完整匹配后直接把：

就可能漏掉重叠匹配。

正确做法是在一次匹配完成以后：

这样继续利用最长相等前后缀。

四十八、一道预测题

主串：

abababa

模式：

aba

匹配位置：

因为：

aba

最长相等前后缀为：

a

长度：

第一次匹配完成以后不用回到 0，而可以继续保留：

这就是 KMP 处理重叠匹配的优势。

四十九、还有一种常见题：根据 next 反推模式串关系

例如已知：

在王道 1 下标语义下说明：

也就是说：

当前位置之前的串存在长度 $k-1$ 的相等前后缀。

所以 next 数组其实编码了：

模式串内部的周期结构。

五十、KMP 中最容易犯的错误

错误 1：对整个模式串求 next[j]

如果问：

通常研究的是：

之前已经匹配成功的部分，而不是直接把当前位置也算进去。

具体取决于题目的 next 定义。

错误 2：把“前缀”和“子串”混为一谈

前缀必须：

从第一个字符开始。

后缀必须：

到最后一个字符结束。

错误 3：把整个串算作前后缀

KMP 讨论的通常是真前缀、真后缀。

否则整个字符串永远与自身相等，定义就失去意义。

五十一、错误 4：看到两个 next 数组不同就认为有一个错

例如：

ababa

可能看到：

也可能看到：

还可能看到王道的另一套形式。

不一定谁错。

第一件事必须问：

数组定义是什么？下标从哪里开始？失配代码写的是什么？

五十二、错误 5：认为 KMP 失配时 $i,j$ 一起回退

错误。

普通 BF 经常调整主串起点。

KMP：

主要调整：

五十三、错误 6：混淆 next 与 nextval

普通 next：

说明“最长可复用前后缀”。

nextval：

在 next 基础上再消除“退过去还是相同字符”的无效比较。

所以：

是优化，不是全新的原理。

五十四、错误 7：比较次数把 j=-1 当成字符比较

例如：

if (j == -1 || S[i] == P[j])

当：

时，由于逻辑短路，通常并没有进行

的字符比较。

如果题目问的是：

字符比较次数

不要把这一步算进去。

这也是前面网站模拟六那题为什么值得怀疑的原因。

五十五、把网站五道模拟题归类

目前页面一共收录 5 道串章节模拟题。(Any Docs)

五十六、本章考试的“识别关键词”

看到这些词，立刻想到对应方法。

“模式匹配”

想到：

“主串指针不回退”

想到：

“最长相等前后缀”

想到：

“重复字符造成无效回退”

想到：

“下一次从哪里开始比较”

模拟：

“比较多少次”

画状态表。

“字符串由重复子串组成”

想到：

和

五十七、考试时手算 next 的最快流程

建议固定成四步。

第一步：确认编号方式

看：

还是：

第二步：只观察模式串

与主串无关。

第三步：找最长相等真前后缀

例如：

abab

最长：

ab

长度：

第四步：根据题目 next 定义换算

千万不要把自己熟悉的数组直接填进去。

五十八、比较次数题固定流程

比如失配：

按顺序写：

1. 本次比较次数 $+1$；

2. 查：

   $$j=next[j]$$

   或

   $$j=nextval[j]$$

3. 不动 $i$；

4. 若：

   $$j=-1$$

   再进入哨兵规则；

5. 下一次真正字符比较时再累计。

五十九、KMP 最核心的逻辑链

如果若觉得这一章很乱，只记住这条链：

其中：

next

解决：

回到哪里？

nextval

解决：

回到那里是不是仍然必错？如果是，再跳。

六十、一张表把 BF、KMP、nextval 分清

六十一、这一章建议真正背下来的只有这些

不是背一大堆 next 数组。

而是：

现代前缀表：

复杂度：

重复子串：

若：

则存在重复周期。

六十二、最后给出一个“做题决策树”

遇到串题：

第 1 问：是不是模式匹配？

不是 → 普通串操作。

是 → 看 BF/KMP。

第 2 问：给没给 next？

给了 → 直接模拟 $i,j$。

没给 → 自己求。

第 3 问：是不是要求 nextval？

是 → 在普通 next 上消除相同字符的无效回退。

第 4 问：问比较次数？

是 → 不推公式，画状态表。

第 5 问：不同资料 next 不一样？

先查：

再查：

最后再比较。

本章考研复习结论

第 4 章“串”本身内容很少，真正具有区分度的就是 KMP。本站当前的模拟题也很好地反映了这一点：基本没有考“串是什么”，而是在反复考 next、nextval、指针跳转和比较次数。Algorithm 部分进一步把 KMP 扩展到了 strStr() 和重复子串判断。(Any Docs)

如果按考研应试优先级，建议做到这个程度：

其中 “会完整模拟 KMP”是最高标准：只要这个真会了，前面所有选择题基本都会自动解决。