串

考研408 数据结构 —— 串（String）

1. 串的基本概念

• 定义：串（String）是由零个或多个字符组成的有限序列。
• 空串：长度为 0 的串。
• 子串：串中任意连续的一段字符组成的串。
• 主串：包含子串的串。
• 字符位置：字符在串中的序号，一般从 1 开始。

---

2. 串的存储结构

2.1 顺序存储

• 类似线性表的顺序存储。
• 使用一维数组存放串的字符序列。
• 特点：
  • 随机存取，效率高。
  • 存储密度高。
  • 插入/删除操作开销大（需要移动大量元素）。

2.2 链式存储

• 类似线性表的链式存储。
• 每个节点存放一个字符，或者存放多个字符的块链。
• 特点：
  • 插入、删除方便。
  • 需要额外的指针域，存储密度低。
  • 不支持随机存取。

---

3. 串的基本操作（抽象定义）

1. StrAssign(&T, chars)：赋值操作，用串常量 chars 生成串 T。
2. StrCopy(&T, S)：复制串 S 到 T。
3. StrEmpty(S)：判断 S 是否为空串。
4. StrLength(S)：返回串 S 的长度。
5. ClearString(&S)：清空串。
6. Concat(&T, S1, S2)：串连接。
7. SubString(&Sub, S, pos, len)：求子串。
8. Index(S, T, pos)：定位操作，在 S 中查找 T。
9. Replace(&S, T, V)：将 S 中出现的子串 T 替换为 V。
10. StrCompare(S, T)：比较两个串大小。

---

4. 串的模式匹配

4.1 朴素模式匹配算法（BF算法）

• 思想：从主串第 i 个字符开始，与模式串逐个字符比较，若失败则主串从 i+1 开始。
• 时间复杂度：最坏情况 $O(nm)$（n 主串长度，m 模式串长度）。
• 考点：
  • 理解主串指针和模式串指针的移动过程。
  • 掌握最坏/最好时间复杂度分析。

4.2 KMP 算法

• 核心思想：利用已匹配的信息，避免主串指针回溯。
• 关键结构：next 数组，记录模式串中前缀和后缀的匹配情况。
• 算法步骤：
  1. 预处理模式串，求 next 数组。
  2. 利用 next 数组进行匹配。
• 时间复杂度：$O(n+m)$。
• 考点：
  • next 数组求法。
  • 主串与模式串的匹配过程。
  • 对比 BF 与 KMP 的复杂度。

---

5. 考研常见考点总结

1. 基础概念
   • 串、子串、主串、空串的定义。
   • 串和线性表的区别（操作逻辑不同）。
2. 存储结构
   • 顺序存储与链式存储的优缺点。
3. 抽象操作
   • 子串提取、连接、比较、替换等常见操作。
   • 常考操作复杂度分析。
4. 模式匹配
   • BF 算法原理与复杂度。
   • KMP 算法的思想与 next 数组计算。
   • 考试重点：手动推导 next 数组。

---

6. 高频易错点

• 子串与子序列的区别：子串必须连续，子序列可以不连续。
• 串与数组/线性表的区别：串是处理字符序列，操作针对模式匹配、子串查找等。
• KMP 的核心：next[j] 表示模式串 P[0..j-1] 的最长相等真前后缀的长度。
• 复杂度分析：BF 算法最坏 $O(nm)$，KMP 算法 $O(n+m)$。

---