串的定义与基本概念

2026 大纲 六（八）字符串模式匹配 的前置概念（大纲无独立的「串」章；匹配算法见《BF》《KMP》）。

串只是「操作粒度被放大」的线性表

把串的定义和线性表的定义摆在一起看，会发现它们几乎是同一句话：串是零个或多个字符组成的有限序列。元素之间一对一，有唯一的开头和结尾——这就是线性表的逻辑结构，一点没变。

真正的差别在操作的对象是谁。线性表的插入、删除、查找，动的都是一个元素；而串的插入、删除、查找，动的是一段连续的字符：StrInsert 插进去的是一个子串，Index 要找的也是一个子串。教材把这叫做"数据元素受限为字符，但操作对象放大到子串"。

这个放大带来的后果，就是这一章唯一值钱的东西。逐个元素地找，扫一遍就完了；而要在长 $n$ 的串里找长 $m$ 的子串，"扫一遍"就不再是显然的事——朴素地做是 $O(nm)$。整个（八）就在回答这一个问题：能不能做到 $O(n+m)$。

所以这一篇的定位很清楚：它是术语和存储的准备工作，真正的算法在 BF 和 KMP。

术语里只有三处会绊人

大部分术语望文生义：主串是包含子串的那个串，串相等是长度相同且逐字符相同。以 $S=\text{’abcabc’}$ 为例，需要单独盯一下的只有三处。

第一，位置从 1 开始数。 'c' 第一次出现在位置 3，不是下标 2。而子串的位置指的是它第一个字符在主串中的位序——'bca' 在 $S$ 中的位置是 2。整套匹配算法的返回值都建立在这个约定上。

第二，"任意个连续字符"里的"任意个"包含两个极端。 取 0 个得到空串，取全部 $n$ 个得到原串本身——所以空串和串本身都是自己的子串。判断"某某是不是 $S$ 的子串"时别把这两头漏掉。

第三，空串不是空格串。 空串长度为 0，一个字符都没有；'␣␣␣' 长度为 3，三个空格都是货真价实的字符。教材在这里特意加了一句"请注意此处不是空串"。判别只有一条：数一数串值里有几个字符。

另有一对区分要放到查找章节去用：子串必须连续，子序列可以跳着取。'abc' 的 'ac' 是子序列但不是子串。模式匹配匹的是连续子串。

数子串：两个长得像的问题，答案不一样

题面里"子串的个数"和"不同子串的个数"是两个问题，而且第二个没有公式。

按位置数时，一个子串由"起点 + 长度"唯一确定。起点 $i$ 可取 $1\sim n$；起点定在 $i$ 之后，长度最多取到 $n-i+1$。于是非空子串共

$$\sum _{i=1}^n(n-i+1)=n+(n-1)+\cdots +1=\frac{n(n+1)}{2}$$

个，含空串再 $+1$。换个角度数也一样：一个非空子串等价于在 $n$ 个字符里选起点和终点（允许重合），即 $(\genfrac{}{}{0ex}{}{n}{2})+n=\frac{n(n+1)}{2}$。

但不同子串的个数由串值决定，不再只由 $n$ 决定：

$S$	按位置的非空子串	不同的非空子串
'abc'	6	6
'aaa'	6（a×3、aa×2、aaa×1）	3（a、aa、aaa）

两个串长度都是 3，按位置数都是 6，去重后一个 6 一个 3。所以看到"不同子串"三个字，只能老老实实逐个列出来去重。

存储：三种方式，但推导链只有一条

教材列了定长顺序、堆式顺序、块链三种，读起来像三个并列选项。其实它们之间有先后：

先看链式为什么不行。 串的一个数据元素只有一个字符（1 字节）。如果一个结点存一个字符，那么每个结点还要挂一个 4 或 8 字节的指针——指针比数据本身大好几倍，存储密度低到不能接受。

于是把结点做大，一个结点存 CHUNKSIZE 个字符，密度是上去了，可新麻烦跟着来：串长不一定是 CHUNKSIZE 的整数倍，最后一个结点会剩空位（通常补 # 之类的非串值字符）；插入删除还要在块内搬字符、块间调整。结点大小成了两难，所以块链存储实际很少用。

回头看顺序存储反而正合适。 串的典型操作是赋值、联接、匹配，不是频繁的单点插删——顺序存储那个"插删要搬移大量元素"的老毛病在串上并不突出；而模式匹配的基本动作是 S[i] 与 T[j] 的比较，正需要 $O(1)$ 的随机访问。结论：串多采用顺序存储。

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN + 1];  // 多开一个位置：下标 0 闲置不用，串值从 ch[1] 开始
    int  length;          // 串的当前长度
} SString;

下标 0 闲置不用，是为了让数组下标与"位置从 1 开始"对齐：S.ch[i] 就是第 $i$ 个字符，匹配成功可以直接返回 i - m；而空出来的 0 恰好拿去做 next 数组"退无可退"的哨兵。如果改成下标从 0 开始，那个哨兵就要写成 $-1$——两种 next 口径的全部差异都源于这一处，做题时先看题面用的是哪一套。

定长与堆式的区别只在"空间什么时候确定"：定长在编译期定死，简单但会截断；堆式（char *ch + malloc）在运行期按实际串长分配，灵活但要自己管释放。

另有一种老写法把串长直接记在 ch[0] 里（T[0] 即串长），连 length 字段都省了。它同样占用下标 0、同样让串值从 1 开始，与上面的约定一致。

十来个操作里，只有一个有算法含量

串的基本操作表看着长，但赋值、复制、求长、比较、求子串、联接、插删子串——全是数组搬运，写出来就是几个 for。注意插入删除的对象是子串而不是单个字符，这正是"操作粒度放大"的直接体现。

唯独 Index(S, T, pos)（子串定位）不一样：在长 $n$ 的主串里找长 $m$ 的模式，怎么才能快。

有意思的是，Index 其实可以由 SubString 和 StrCompare 拼出来——逐个位置取子串再整体比较，功能完全正确。所以它不在"最小操作集"里。但这样拼出来的版本要反复复制子串，效率极差。为它单独设计一个不依赖其他操作的算法，正是 BF 与 KMP 的由来。

基本操作全表（题面给了某个操作名、或要写 ADT 时展开）

操作	说明
StrAssign(&T, chars) / StrCopy(&T, S)	赋值 / 复制
StrEmpty(S)	判空（判的是空串，不是空格串）
StrLength(S)	求串长
StrCompare(S, T)	比较大小（按字典序，逐字符比编码值）
SubString(&Sub, S, pos, len)	求子串：从 pos 起取长度 len
Concat(&T, S1, S2)	联接
Index(S, T, pos)	定位：从 pos 起求 T 在 S 中首次出现的位置
Replace(&S, T, V)	用 V 替换 S 中所有与 T 相等且不重叠的子串
StrInsert(&S, pos, T) / StrDelete(&S, pos, len)	插入 / 删除一个子串

模式匹配问题：分水岭只有一条

把 Index 单独拎出来，就是模式匹配问题：

输入：主串 $S{=}^{\prime }{s}_1{s}_2\cdots s_n$'（也称正文串）、模式串 $T{=}^{\prime }{t}_1{t}_2\cdots t_m$'（也称模式），$T$ 非空。 输出：$T$ 在 $S$ 中首次出现时，其第一个字符在 $S$ 中的位置；若不存在，返回 0。

这三条约定每一条都会在题目里用到：返回的是首次出现（后面还有也不管）、失败返回 0（0 不是合法位置，所以能拿来当失败标志）、匹配的是连续子串。

两个算法的分水岭只有一条：失配的时候，主串指针 $i$ 要不要退回去。

BF 要退，因为它什么都不记得——上一轮比对过的 $j-1$ 个字符，失配的一瞬间信息全丢，只能从头再来。KMP 不退，因为那 $j-1$ 个字符本身就是模式串的前缀：既然它们等于 $T$ 的前 $j-1$ 位，那么"它们内部有多长的前后缀重合"这件事，与主串完全无关，可以在拿到模式串的那一刻就算好。

一句话：KMP 把运行时的重复比较，换成了预处理阶段的一次性计算。 这句话是整章的主线，后两篇都在展开它。

考点速记

三条会被反复调用的结论：

1. 串与线性表的差别在操作粒度，不在逻辑结构——正因为对象从"一个元素"放大到"一段连续元素"，才有了模式匹配问题。
2. 串这一章的算法含量全部集中在 Index 一个操作上，其余操作都是数组搬运。
3. BF 与 KMP 的唯一分水岭是"失配时主串指针要不要回退"；不回退之所以可能，是因为已匹配的那段内容本身就是模式串的前缀，能离线预处理。

这一节在 408 真题里不单独成题。 整个「串」章的真题（下方「真题练习」）全部落在 KMP 上——2015、2019、2024 三道，考的都是 next 数组与匹配过程，没有一道考子串计数、存储结构或基本操作。术语和存储在这里的作用是读懂题面，不是答题点本身：

• 位置从 1 开始、下标 0 闲置——这个约定直接决定了 next 数组是哪一套口径，是三道真题的共同前提。
• 子串必须连续——匹配匹的是连续子串，不是子序列。

所以这一篇看懂即可，时间要留给 KMP。

易错：把"子串个数"和"不同子串个数"当成一个问题。 前者恒为 $\frac{n(n+1)}{2}$，后者要逐个去重、没有公式。

易错：空串与空格串混为一谈。 长度 0 和长度 3，StrEmpty 只对前者返回真。

易错：忘了空串和串本身也是子串。 "任意个连续字符"的两个端点都算数。

教材出处

• 严蔚敏、李冬梅、吴伟民《数据结构（C 语言版）》（第 2 版），第 4 章 4.1 节，印刷第 87–88 页：串的定义、串值与串名、子串与主串、字符位置与子串位置、串相等的判定，以及"一个或多个空格组成的串称为空格串，请注意此处不是空串"。
• 同书 4.3.1 节，印刷第 89–90 页：串的抽象数据类型定义，含 StrAssign、StrCompare、Index、Replace、StrInsert、StrDelete 等基本操作。
• 同书 4.3.2 节，印刷第 90–91 页：定长顺序存储（#define MAXLEN 255、char ch[MAXLEN+1]，并明确"下标为 0 的分量闲置不用"）、堆式顺序存储 HString、块链存储 CHUNKSIZE 与存储密度的讨论。
• 同书 4.3.3 节，印刷第 91–92 页：模式匹配问题的提法（主串／正文串、子串／模式、返回首字符在主串中的位置）。

相关知识

朴素模式匹配（BF）（Index 最直接的实现，也是"回退浪费"的对照组）｜ KMP 算法（用 next 数组消掉主串指针回退）｜ 从 KMP 到工业级全文搜索（超纲延伸）｜ 线性表的基本概念（同一逻辑结构）｜ 查找的基本概念（按关键字等值比较，不包含字符串模式匹配）

相关文章

• 朴素模式匹配（BF 算法）
• KMP 算法
• 拓展：从 KMP 到工业级全文搜索

真题练习

相关真题（3题）

2024Q62分2019Q92分2015Q82分