本文共 2800 字，大约阅读时间需要 9 分钟。

串（数据结构）与模式匹配算法

前言

串是我们所说的字符串，计算机对数据的处理主要包括数值计算和非数值计算。在计算机发展的早期，数值计算比较普遍，但随着社会需求的不断增长，非数值处理的计算越来越多。其中，最复杂的非数值处理往往是对字符串的处理。字符串数据的处理比整型或浮点型数据的处理复杂得多，因此将串作为一种独立的数据结构进行研究是必要的。

串导学

1. 课程结构

本课程的主要内容包括：

• 数据结构、抽象数据类型（ADT）、算法
• 线性表
• 栈和队列
• 字符串
• 数组与广义表
• 树和二叉树
• 图

2. 知识点搜索

字符串是一种线性结构，其存储可以有顺序表和链式两种实现方式。与线性表相比，串的操作有一些特殊之处，这些操作主要针对串的特有功能进行设计。

在C/C++中，字符串更多地被视为一种数据类型，但在本课程中，我们将其视为一种数据结构。串的特殊性体现在以下几个方面：

串的应用非常广泛，例如搜索引擎中的字符串查找匹配、文字处理软件（如WPS Office）、生物信息处理等。这些应用都离不开对字符串进行处理的能力。

3. 串的特点

串是一种特殊的线性表，其与普通线性表的主要区别在于：

• 数据元素类型为字符。
• 操作对象是子串，而不是单个元素。
• 一些操作具有特定的实现方式，例如模式匹配。

串的作用主要体现在以下几个方面：

串的基本概念

1. 串的定义

串由零个或多个字符组成的有限序列组成。需要注意的是：

• 空串是由零个字符组成的串，通常用$\Phi$表示。
• 空串与空格串是不同的概念。
• 串的长度是字符的个数，记作$n$。
• 串的表示为$S = a_1a_2…a_n$，其中$a_i$表示第$i$个字符。

例如：

• 空串$\Phi$的长度为$0$。
• 串$S = "abcde"$的长度为$5$。

2. 串的操作

串的操作主要包括：

• 串相等：两个串相等当且仅当它们的长度相等，且对应位置的字符完全相同。
• 子串：是串中任意个连续字符组成的子序列，包括空串。
• 真子串：不包含自身的所有子串。例如，"abcde"的真子串共有$15$个（包括空串）。

3. 串的基本操作

串的操作主要包括插入、删除、链接、求子串、替换等。这些操作的实现方式与普通线性表类似，但由于操作对象是子串，因此有一些特殊之处。

4. 串与线性表的关系

与普通线性表相比，串的主要特点包括：

• 相同点：
  • 数据元素类型相同（均为字符）。
  • 操作包括子串操作（如模式匹配）。
• 区别点：
  • 操作对象是子串而非单个元素。
  • 部分操作具有特定的实现方式，例如模式匹配。

模式匹配

1. 模式匹配的定义

模式匹配是串处理中的重要操作，其目标是找到主串$T$中是否存在某个子串$P$。具体来说：

• 主串$T$：目标字符串。
• 模式串$P$：待匹配的字符串。
• 结果：如果$T$中存在与$P$相等的子串，则返回匹配的起始位置；否则返回$0$。

例如：

• 主串$T = "Beijing"$，模式串$P = "jin"$。匹配结果为$3$（从$0$开始计数）。

2. 模式匹配的应用

模式匹配的应用领域非常广泛，例如：

• 自然语言处理：信息检索。
• 生物信息处理：DNA序列匹配。
• 语音识别：语音符号化。
• 网络安全：病毒检测。

3. 模式匹配的作用

以生物信息处理为例：

• 研究者将DNA序列表示为字符串形式。
• 通过模式匹配算法检测病毒DNA是否存在于患者DNA中。
• 例如：
  • 病毒DNA序列为"baa"。
  • 患者1的DNA序列为"a aabb ba"，则匹配成功。
  • 患者2的DNA序列为"babbba"，则匹配失败。

BF算法

1. 算法概述

BF算法（Backtracking Algorithm）是最简单的模式匹配算法，采用回溯法实现。其核心思想是：

2. 算法过程

BF算法的实现步骤如下：

3. 算法特点

• 简单易懂。
• 每次匹配失败时，都会回溯到上次匹配的位置+1。
• 搜索效率较低，每次匹配失败时需要重新开始。

4. 算法复杂度

• 最好情况复杂度：$O(m)$。
• 最坏情况复杂度：$O(n \cdot m)$。

KMP算法

1. 算法来源

KMP算法由Donald E. Knuth、James H. Morris和V. R. Pratt同时发明。其名称来源于这三个人的名字的首字母缩写。

2. 算法改进点

BF算法的主要缺点是每次匹配失败时都需要回溯到上次匹配的位置。KMP算法通过预处理失败函数，避免不必要的回溯。

• 失败函数：记录模式串中每个位置$j$的下一个匹配位置$k$。
• 有效匹配：当模式串与主串不匹配时，保持主串指针$i$不回溯，仅调整模式串指针$j$。

3. KMP算法的核心

4. 失败函数的定义

失败函数$next[j]$的定义：

• 如果$P[j] == P[j+1]$，则$next[j] = next[j+1]$。
• 否则，$next[j] = j + 1$。

5. 时间复杂度

• 预处理失败函数的时间复杂度：$O(m)$。
• 实际匹配的时间复杂度：$O(n + m)$。

总结

1. 串数据结构的特点

• 数据对象限定了字符集。
• 操作对象是一组数据元素。
• 操作具有特定的实现方式，例如模式匹配。

2. 模式匹配算法：BF、KMP

• BF算法简单易懂，但效率较低。
• KMP算法通过失败函数和有效匹配优化，效率显著提升。
• KMP算法的时间复杂度为$O(n + m)$，比BF算法更高效。

通过本课程的学习，我们掌握了串数据结构的基本概念、操作及其实现方式，同时熟悉了BF算法和KMP算法的工作原理。这些知识在自然语言处理、生物信息处理等领域具有重要应用价值。