淮南便民网_qq营销推广方法和手段_资源网站快速优化排名_潍坊seo按天收费

前言

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在文本中快速查找特定子串的位置。其核心思想是通过预处理模式串（待查找的子串），避免在匹配失败时进行不必要的回溯，从而将时间复杂度优化为 O(n + m)（n为文本长度，m为模式串长度），显著优于暴力算法的O(n*m)。

---

核心原理

1. 部分匹配表（Partial Match Table, PMT）

• 预处理模式串，生成一个长度与模式串相同的数组（PMT）。
• PMT[i] 表示模式串前 i+1 个字符的最长公共前后缀长度（即前缀和后缀的最长重合部分）。
• 示例：模式串 "ABABC" 的 PMT 为 [0, 0, 1, 2, 0]。

2. 匹配时的智能跳转

• 当文本与模式串的某字符不匹配时，根据 PMT 的值移动模式串的位置，跳过已匹配的部分前缀，避免重复比较。
  （这里不理解的同学不要担心继续看下去，下面会做一个详细的示例来解释这个过程。）

---

算法步骤

1. 构建PMT表

• 1.初始化两个指针（前缀指针和后缀指针）。

   在理解部分匹配表之前，需要先明白字符串前缀和后缀的概念：前缀：指除了最后一个字符以外，一个字符串的全部头部组合。
例如，对于字符串 "ABCD"，它的前缀有 "A"、"AB"、"ABC"。这里可以简单的理解为从头到尾遍历字符串，一次最少一个字符。并且每次都比上一次多一个，最后一个不参与。后缀：指除了第一个字符以外，一个字符串的全部尾部组合。
例如，对于字符串 "ABCD"，它的后缀有 "BCD"、"CD"、"D"。这里可以简单的理解为从尾到头遍历字符串，一次最少一个字符。并且每次都比上一次多一个，第一个不参与。

• 2.部分匹配表（前缀函数）的构建

部分匹配表记录了模式串中每个位置之前的子串的最长公共前后缀的长度。构建部分匹配表的过程如下：

假设模式串为 pattern，我们使用一个数组 next 来存储部分匹配值，next[i] 表示模式串中从 0 到 i 这个子串的最长公共前后缀的长度。所以部分匹配表的长度和模式串的长度是一致的。

以下是构建部分匹配表的步骤：

• 初始化：next[0] = 0，因为只有一个字符时，不存在前后缀，最长公共前后缀长度为 0。
• 从 i = 1 开始遍历模式串：
  • 设 j 为当前最长公共前后缀的长度，初始时 j = 0。
  • 当 pattern[i] == pattern[j] 时，说明找到了更长的公共前后缀，j 加 1，next[i] = j，然后 i 加 1 继续比较下一个字符。
  • 当 pattern[i] != pattern[j] 时，需要回溯 j 的值。让 j = next[j - 1]，这是因为我们要利用之前已经计算好的部分匹配值，尝试找到一个更短的公共前后缀，继续比较 pattern[i] 和 pattern[j]，直到 pattern[i] == pattern[j] 或者 j 为 0。

2. 文本匹配

• 使用双指针分别遍历文本和模式串。
• 遇到不匹配时，根据 PMT 回退模式串指针，继续匹配。
  （这里不理解的同学不要担心继续看下去，下面会做一个详细的示例来解释这个过程。）

---

示例说明

假设在文本 “ABABABCABABC” 中查找模式串 “ABABC”：

模式串："ABABC"
文本："ABABABCABABC"

我们的第一个步骤是为模式串构建部分匹配表（Partial Match Table, PMT）。
这里我们需要先理解什么是部分匹配表（Partial Match Table, PMT）

模式串 “ABABC” 的 PMT 表构建详细步骤分解

模式串索引：0:A, 1:B, 2:A, 3:B, 4:C
目标：计算每个位置 i 的 PMT 值（即前 i+1 个字符的最长公共前后缀长度）。

---

1. 初始化

• PMT数组：pmt = [0, 0, 0, 0, 0]
• 前缀指针 j：初始化为 0（从模式串开头开始）。
• 后缀指针 i：从 1 开始遍历（因为单个字符无前后缀）。

---

2. 计算 pmt[0]

• 前 1 个字符："A"
• 前缀：无（单个字符无前缀）。