当前位置：首页 > news >正文

【数据结构与算法】Knuth-Morris-Pratt 算法（KMP算法）：一种在字符串中查找子串的算法

news 2025/6/6 10:30:28

引言

KMP（Knuth-Morris-Pratt）算法是一个在字符串中查找子串的算法，由 Donald Knuth、Vaughan Pratt 和 James H. Morris 共同发明。这个算法的特点是在查找过程中，不会回溯主串，也不会重复扫描已经比较过的子串，因此它的时间复杂度是线性的。它的主要优点是在比对过程中，当一个字符不匹配时，可以跳过一些无需再次比对的字符，从而提高匹配效率。

基本思想

KMP算法的主要思想是利用已经部分匹配的有效信息，使得后续的匹配可以跳过那些已知肯定不会匹配的字符。

KMP 算法的核心是一个叫做部分匹配表（Partial Match Table, PMT）或者失败函数的预处理过程。这个表格记录了子串的前缀集合与后缀集合的最长公共元素的长度。在查找过程中，如果发生字符不匹配，我们可以通过这个表格快速移动子串的位置，跳过一些不可能匹配的位置。

例如，对于字符串"ABCDABD"，其部分匹配表如下：

字符	A	B	C	D	A	B	D
PMT	0	0	0	0	1	2	0

这个表的意思是，在模式串中，位置i之前的子串的最长公共前后缀的长度是PMT[i]。例如，位置5之前的子串是"ABCDAB"，它的最长公共前后缀是"AB"，长度是2，所以PMT[5]=2。

当在主串中进行匹配时，如果遇到不匹配的字符，可以利用部分匹配表中的信息，将模式串向右滑动一定的距离，从而跳过一些肯定不会匹配的位置，提高匹配效率。

在计算部分匹配表时，通常会使用动态规划的思想，对每个位置，都检查它之前的所有子串，找出最长的那个公共前后缀。

这个部分匹配表在KMP算法中有一个非常重要的作用，那就是当模式串中的某个字符与主串不匹配时，可以根据这个表直接跳过一部分字符，而不需要一个一个地去比对。

通过这种方法，KMP 算法可以在 O(n+m) 的时间复杂度内完成字符串的查找任务，其中 n 是主串的长度，m 是子串的长度。

详细步骤

预处理阶段
生成部分匹配表。对于每个位置 i，我们计算子串 s2[1...i] 的最长相等的真前缀和后缀的长度 pmt[i]。这个长度就是当 s2[i+1] 和主串的某个字符不匹配时，我们需要将子串移动到的位置。

	const int N = 1e7 + 7;string s1, s2;int pmt[N];cin >> s1 >> s2;s1 = " " + s1;s2 = " " + s2;int l1 = s1.length() - 1;int l2 = s2.length() - 1;int j;	// 当前已经匹配的字符数量// 生成部分匹配表j = 0;for (int i = 2; i <= l2; i++) {// 下一个字符不匹配while (j && s2[i] != s2[j + 1]) {// 向前回溯j = pmt[j];}// 下一个字符匹配if (s2[i] == s2[j + 1]) {// j 后移一位j++;}// 更新部分匹配表pmt[i] = j;}

查找阶段
从左到右扫描主串，同时移动子串的位置。如果主串的某个字符和子串的当前字符不匹配，我们就通过部分匹配表移动子串的位置。具体的移动方法是，将子串的位置向右移动 i - pmt[i] 个位置，其中 i 是子串中最后一个与主串匹配的字符的位置。

	// 查找字符串j = 0;for (int i = 1; i <= l1; i++) {// 下一个字符不匹配while (j && s1[i] != s2[j + 1]) {// 向前回溯j = pmt[j];}// 下一个字符匹配if (s1[i] == s2[j + 1]) {// j 后移一位j++;}// 匹配到字符串if (j == l2) {cout << i - l2 + 1 << endl;// 向前回溯，继续查找j = pmt[j];}}