Appearance
串的定义与基本概念
核心思想
串的定义
串（String）是由零个或多个字符组成的有限序列，记为：
S = 'a₁a₂...aₙ'其中：
- n 为串的长度，即字符的个数
- n = 0 时称为空串，记为 ∅ 或 ""
- 串中的每个字符都有一个序号，称为该字符在串中的位置（从 1 开始计）
基本术语
| 术语 | 定义 | 示例（S = 'abcabc'） |
|---|---|---|
| 子串 | 串中任意个连续字符组成的子序列 | 'abc'、'bca'、'a' |
| 主串 | 包含子串的串 | S 是 'abc' 的主串 |
| 空串 | 长度为 0 的串 | "" |
| 空格串 | 由空格字符组成的串 | ' '（长度为 3） |
| 串相等 | 长度相同且对应位置字符相同 | 'abc' = 'abc' |
| 子串位置 | 子串第一个字符在主串中的位序 | 'bca' 在 S 中的位置是 2 |
空串 ≠ 空格串：空串长度为 0，空格串长度为空格字符的个数。这是 408 选择题的常见陷阱。
串的基本操作
| 操作 | 说明 |
|---|---|
| StrAssign(&T, chars) | 赋值，将字符串常量 chars 赋给 T |
| 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 中的位置 |
其中 Index 操作就是模式匹配问题，是本章的算法核心。
串的存储结构
| 存储方式 | 实现 | 特点 |
|---|---|---|
| 定长顺序存储 | 用静态数组 char str[MaxLen] | 长度固定，超出则截断 |
| 堆分配存储 | 用 malloc 动态分配 | 长度可变，C 语言的标准实现 |
| 块链存储 | 用链表，每个结点存多个字符 | 存储密度低，实际很少使用 |
408 考研中，串的存储结构较少单独出题，重点在算法层面。但需要注意：
- 定长顺序存储中，串的长度通常有两种记录方式：下标 0 位置存长度 或 用 '\0' 标记结尾
- KMP 算法的实现中，串的下标从 0 开始还是从 1 开始会影响 next 数组的值，做题时务必看清题目约定
模式匹配问题
串这一章的算法核心是模式匹配（Pattern Matching）：
给定主串 S 和模式串 T，在 S 中找到 T 第一次出现的位置。
BF 算法是理解匹配过程的基础，KMP 算法是 408 的核心考点。两者的本质区别在于：失配时主串指针 i 是否需要回退。
考研高频考点
- ⭐ KMP 算法的 next 数组 / nextval 数组手算（大题高频，几乎年年考）
- ⭐ KMP 算法的匹配过程模拟（选择题/填空题）
- 串的基本概念辨析：空串 vs 空格串（选择题）
- 子串个数的计算：长度为 n 的串有 n(n+1)/2 + 1 个子串（含空串）
- BF 算法与 KMP 算法的时间复杂度对比
易错：串的子串个数容易算错。长度为 n 的串，非空子串有 n(n+1)/2 个（长度为 1 的有 n 个，长度为 2 的有 n-1 个，...，长度为 n 的有 1 个），加上空串共 n(n+1)/2 + 1 个。注意：相同内容的子串在不同位置算不同子串。
相关知识
- 朴素模式匹配（BF 算法）：最直观的暴力匹配方法
- KMP 算法：利用部分匹配信息避免回退的高效算法