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

KMP模式匹配算法——详细讲解、清晰易懂

article 2024/12/24 0:21:32

KMP算法介绍

KMP算法是由D.E. Knuth、J.H. Morris和V.R. Pratt(其中Knuth和Pratt共同研究, Mor-ris独立研究)发表一个模式匹配算法，KMP算法的最大特点使得它在处理大量文本匹配的问题时，比暴力枚举算法有更好的性能。

关于字符串匹配，是字符串很重要的知识点，也是面试笔试的高频考点。Leetcode的第28题就是考查字符串匹配算法。另外本文是查看了《大话数据结构》这本书做的总结，同时next数组部分也参考了这篇博客KMP算法中next数组的计算。

KMP是由基础的字符串匹配BF算法改进而来的，具体可以看下之前发布的BF算法图解

KMP模式匹配算法原理

目标串（主串） S = “heloohello”, 模式串（子串） T = “hello”。我们要从主串 S 中找到子串 T 的位置。如果使用BF算法，步骤如下图所示。

在 ① 中当 S 和 T 不匹配时，BF算法的操作是主串 S 回退到 i-j+1（从本次匹配的初始位置后移一位，图中步骤②的位置），匹配串 T 回退到 j = 0 (初始位置）, 然后执行 ②③④⑤⑥ 步依次进行匹配，但所有这些步骤一定都是必需的吗？

.
在步骤 ① 中，单看模式串 T，前三个字符均不相等（‘h’ != ‘e’ != ‘l’），同时S 和 T 串前三个字符又相匹配，那么模式串 T 的首字符’h’ 自然不可能和主串 S 的第二、三位字符相等。所以步骤②③都是多余的。这是KMP算法的关键所在，如果我们知道 T 串中哪些字符相等（也是关键点，后续会讲），那么有些步骤就可以省略。

因此只需要保留①④⑤⑥的步骤即可。从下图可以看出，指针 i 是不是一直没有回溯？这就是KMP的妙处所在。在KMP中，指针 i 永远不会回溯，只有指向模式串的指针 j 会发生回溯。在本例中 j 每次都回退到首元素，我们再举一个例子，看看 j 会怎么变化。

第二个例子：

目标串（主串） S = “abcababca”, 模式串（子串） T = “abcabx”。BF算法执行过程如下图所示，在步骤 ① 中前5个字符完全相等，根据上一个例子的经验，已知模式串T中第一位字符与第二位、第三位不等（后续会根据next[]数组计算得出），步骤 ②③ 都是多余的，直接省略。

与上个例子不同的是，这里的模式串 T 的首位字符 'a' 与 T 第四位的 'a' 相等，第二位的 'b' 与第五位的 'b' 相等，而在 ① 中,第四位的 'a' 第五位的 'b' 已经与主串 S 中的相应位置比较过了，是相等的。因此可以断定,T 的首字符 'a'、第二位的字符 'b' 与 S 的第四位字符和第五位字符肯定也是相等的，所以 ④⑤ 这两个比较得出字符相等的步骤也可以省略。

总结上面两个例子，在KMP算法中，主串的 i 值是不需要回溯的。所以我们只需要考虑变化的 j 值，模式串 j 值的变化通过观察可以发现，当主串和模式串不匹配时，下一步 j 该指向哪个元素只与模式串 T 本身有关系。当发现有相同的字符，j 的变化也就会不同。

在KMP中，当主串和模式串不匹配时, 下一步 j 值的多少取决于当前字符之前的串的前后缀的相似度。

next数组

基础知识

在我们计算next数组之前，我们先讲解一些基础知识。

前缀：字符串的开头，例如字符串abcd的前缀为a, ab, abc, abcd。在KMP算法中使用的前缀为真前缀，既不包括原字符串abcd的前缀。（真前缀：a, ab, abc）
后缀：字符串的结尾，在KMP算法中同样使用的是真后缀(bcd,cd,d)。
最长公共前后缀：最长的相等的前缀与后缀，例如字符串ABCxyzABC的最长公共前后缀为ABC
- ABCXYABC的真前缀：A，AB, ABC, ABCx, ABCxy, ABCxyz, ABCxyzA, ABCxyzAB
- ABCXYABC的真后缀：BCxyzABC, CxyzABC, xyzABC, yzABC, zABC, ABC, BC, C
前缀表：存储每一个前缀的最长公共前后缀的长度。
举例：若模式串 T=“abaaabaaca”。

- next数组：把 T 串各个位置的 j 的变化定义为数组 next，next 的长度就是 T 串的长度。主串和模式串不匹配时，下一步 j 的值由 next[j] 决定。例如目标串 S="abcaba", T="aba", 根据前缀表求出 next=[-1,0 0], 当 j=2 时发生不匹配, next[2]=0, 下一步 j 将等于 0 进行字符匹配。

前缀表和next数组的关系

前缀表存储每一个前缀的最长公共前后缀的长度，next数组存储的是模式串向右移动到next值的位置，这个值与前缀的最长公共前后缀的长度有关，所以next数组是可以由前缀表生成的。
用前缀表生成一个next数组很容易，将前缀表每一位都向后移动1位（最后一位舍去）并在第一位补一个-1就得到了next数组。

如果有同学不理解这个关系还可以看一下手动推理过程：
T=“abaaabaaca”

位置0上的元素a前面没有子串，令next[0]=-1
位置1上的元素b前面的字符串为"a"，字符串"a"没有最长公共前后缀，next[1]=0
位置2上的元素a前面的字符串为"ab","ab"没有最长公共前后缀，next[2]=0
位置3上的元素a前面的字符串为"aba"，最长公共前后缀为"a"，next[3]=1
位置4上的元素a前面的字符串为"abaa"，最长公共前后缀为"a"，next[4]=1
位置5上的元素b前面的字符串为"abaaa"，最长公共前后缀为"a"，next[5]=1
位置6上的元素a前面的字符串为"abaaab"，最长公共前后缀为"ab"，next[6]=2
位置7上的元素a前面的字符串为"abaaaba"，最长公共前后缀为"aba"，next[7]=3
位置8上的元素a前面的字符串为"abaaabaa"，最长公共前后缀为"abaa"，next8]=4
位置9上的元素a前面的字符串为"abaaabac"，没有最长公共前后缀，next[9]=0

同时在KMP算法中next数组的计算这篇博客中提到了一个地方：为什么有些next数组是0,1开头，而有些next数组是-1,0开头？

-1,0开头与0, 1开头的next数组本质是一样的。实际上，以0, 1开头的next数组就是以-1,0开头的next数组每一项加1得到的。出现这种情况的原因在于模式串起始的索引值：在程序中，一个数组的索引的起始值为0；然而在考试和书中给的模式串起始值是多从1开始。所以在考试中遇到的next数组通常是以0, 1开头；而一些程序或教程中的next数组是以-1, 0开头。

注：在考试中通常会给模式串的索引，或者会给next值的前两项，在答题时要按照题目中的要求写next数组。

代码实现

next数组的代码实现, 可以计算出当前匹配串 T 的 next 数组

void get_next(string T, int *next) {
	next[0] = -1;
	int i = 0;
	int j = -1;
	
	while(i < T.size() - 1) {
		//T[i]表示后缀的单个字符
		//T[j]表示前缀的单个字符
		if(j == -1 || T[i] == T[j]){//
			++i;
			++j;
			next[i] = j;
		} else {
			//如果字符不相同，则j值回溯
			j = next[j];
		}
	}
}

KMP代码实现

int KMP(string S, string T) {
    int ans = -1;
    // i用于遍历主串S
    int i = 0;
    // j用于遍历匹配串T
    int j = 0;
    int next[255]; // 这里初始长度为255,需自行调整
    // 对T做分析，得到next数组
    get_next(T, next);
    while (i < S.size()) {
        // 匹配成功则继续向下一个字符进行匹配
        if (j == -1 || S[i] == T[j]) {
            ++i;
            ++j;
        }
        // 匹配失败进行回溯
        else {
            // j回溯到合适的位置
            j = next[j];
        }
        if (j == T.size()) {
            ans = i - T.size();
            break;
        }
    }
    return ans;
}