算法与数据结构 算法分析课程 第11章 字符串匹配 字符串匹配算法 KMP算法 共11页.pptx

### 字符串匹配算法概述 在计算机科学领域中，字符串匹配是一种常见的操作，它涉及到在一个较大的文本串（T）中查找一个较短的模式串（P）。本章节将重点介绍字符串匹配的基本概念以及两种重要的算法——简单字符串匹配算法和KMP算法。 #### 一、简单字符串匹配算法 简单字符串匹配算法是最基础的一种方法，其基本思想是从文本串的第一个字符开始，逐个比较文本串中的字符与模式串中的字符是否相同。如果全部字符都匹配，则表示找到模式串；如果有任何字符不匹配，则将模式串向右移动一位，重新开始比较。这种算法的时间复杂度较高，在最坏的情况下为O(nm)，其中n是文本串的长度，m是模式串的长度。 #### 二、KMP算法 KMP算法（Knuth-Morris-Pratt算法）是由Donald Knuth、James H. Morris和Vaughan Pratt共同提出的，它是一种高效的字符串匹配算法，能够显著减少不必要的比较次数，从而提高搜索效率。KMP算法的核心在于构建一个“失败函数”，通过这个函数可以避免重复检查已经匹配过的部分，进而实现高效匹配。 ### KMP算法详解 #### 1. 失败函数 在KMP算法中，“失败函数”是非常关键的概念。对于模式串P，定义一个长度为m的数组`fail[]`，用于记录每个位置的“最大相等前缀长度”。具体来说，对于模式串P中的第k个字符，`fail[k]`的值表示模式串P的前k个字符中最长的前后缀相等的子串的长度加1。例如，对于模式串"ABABABCB"，其`fail[]`数组如下： | k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---|---|---|---|---|---|---|---|---| | P | A | B | A | B | A | B | A | B | | fail[k] | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 这里，`fail[8]`的值为6，表示模式串的前7个字符"AABABAB"中有最长长度为5的前后缀相等的子串"ABAB"。 #### 2. 构建失败函数 为了构建失败函数，需要从模式串的第一个字符开始遍历，直到最后一个字符。对于每个字符，计算出对应的`fail[k]`值。具体的计算规则如下： - 对于每一个位置k（1 ≤ k < m），计算`fail[k]`的值。 - `fail[k]`的值等于所有满足0 ≤ l < k且p[1..l-1]是p[1..k-1]的后缀的最大l值+1。 - 例如，对于模式串"ABABABCB"，当k=8时，最长的前后缀相等的子串为"ABAB"，长度为4，因此`fail[8]`的值为5。 #### 3. 应用有限自动机进行模式匹配 KMP算法可以看作是一种有限自动机的应用。在这种情况下，自动机有两个类型的节点：读节点和停止节点。读节点用于读取文本串中的下一个字符，而停止节点则表示找到了匹配的模式串。每个箭头都标记有一个来自字符集的字符，根据读取到的字符选择相应的箭头前进。 #### 4. KMP流图示例 考虑一个仅包含三个字符（A、B、C）的模式串，我们可以构造一个有限状态机流图来辅助理解KMP算法的工作原理。例如，对于模式串"ABABABCB"，可以通过构建相应的流图来直观地展示匹配过程中的状态转换。 #### 总结 KMP算法通过对模式串进行预处理得到“失败函数”，并在实际匹配过程中利用该函数避免了不必要的回溯，从而大大提高了匹配效率。相比简单的字符串匹配算法，KMP算法的时间复杂度为O(n+m)，其中n是文本串的长度，m是模式串的长度。这种方法不仅理论上有优势，在实际应用中也表现出色，被广泛应用于文本检索、生物信息学等多个领域。