挑战最通俗的KMP算法讲解

什么是 \(KMP\)

KMP是一种用于模式串匹配问题的算法。 给出一个文本串和模式串，查询模式串在文本串中的(出现次数、出现位置等等)的问题称为“模式串匹配问题”。 KMP算法的本质是：针对模式串构建一个特定的数组，用于在匹配失败时减少后续匹配过程中的无用比较，可以将时间复杂度优化到 线性 .

\(next\) 数组

设文本串为 \(s\) ，长度为 \(n\) ；模式串为 \(t\) ，长度为 \(m\) 。 预处理一个 \(next\) 数组，对于 \(next[i]\) ，它表示在 \(t\) 的前 \(i\) 个字母中，最长公共前后缀的长度。 什么意思呢？我们举个栗子： 比如 \(t\) 是 \(ababaca\) ，则对应的 \(next\) 数组如下所示:

\(i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
\(next[i]\)	\(0\)	\(0\)	\(1\)	\(2\)	\(3\)	\(0\)	\(1\)

\(next[1]\) ：前缀：{空}；后缀：{空}。 \(next\) ： \(0\) \(next[2]\) ：前缀：{ \(a\) }；后缀：{ \(b\) }。 \(next\) ： \(0\) \(next[3]\) ：前缀：{ \(\color{red}a\) , \(ab\) }；后缀：{ \(\color{red}a\) , \(ba\) }。 \(next\) ： \(1\) \(next[4]\) ：前缀：{ \(a\) , \(\color{red}ab\) , \(aba\) }；后缀：{ \(b\) , \(\color{red}ab\) , \(bab\) }。 \(next\) ： \(2\) \(next[5]\) ：前缀：{ \(a\) , \(ab\) , \(\color{red}aba\) , \(abab\) }；后缀：{ \(a\) , \(ba\) , \(\color{red}aba\) , \(baba\) }。 \(next\) ： \(3\) \(next[6]\) ：前缀：{ \(a\) , \(ab\) , \(aba\) , \(abab\) , \(ababa\) }；后缀：{ \(c\) , \(ac\) , \(bac\) , \(abac\) , \(babac\) }。 \(next\) ： \(0\) \(next[7]\) ：前缀：{ \(\color{red}a\) , \(ab\) , \(aba\) , \(abab\) , \(ababac\) }；后缀：{ \(\color{red}a\) , \(ca\) , \(aca\) , \(baca\) , \(abaca\) , \(babaca\) }。 \(next\) ： \(1\) 。

如何进行匹配？

这里我们先假设我们已经求出了 \(next\) 数组（马上讲怎么求），我们来看看怎么进行匹配。 因为“next”这个词有可能被判断为关键字，所以接下来我们用“ne”来表示。 首先我们建立两个指针，分别为文本串的和模式串的.

                        
                          int i = 0, j = 0;

                        
                      

然后，当文本串的指针还没有到达终点时，我们就接着匹配.

                        
                          while (i < s.size()) {
    ...
}

                        
                      

如果当前的字母匹配，那就把两个指针都往后移一个字符.

                        
                          if (s[i] == t[j]) i++, j++;

                        
                      

如果不匹配，那就把 \(j\) 挪动 \(next[j - 1]\) 格.

                        
                          else if (j > 0) j = ne[j - 1];

                        
                      

如果还是不行，说明这是第一格就不匹配，把 \(i\) 往后挪.

                        
                          else i++;

                        
                      

如果 \(j\) 到了终点，说明匹配成功。返回模式串匹配的起始坐标即可.

                        
                          if (j == t.size()) return i - j;

                        
                      

\(next\) 数组的原理 & 如何求 \(next\) 数组？

刚才我们说了：如果不匹配，那就把 \(j\) 挪动 \(next[j - 1]\) 格。为什么可以这么做呢?

（这里用了一个b站大佬的图） 如上图，可以发现，我们成功匹配的画黄线的两个 \(AB\) ，和前面跳过的画蓝线的两个 \(AB\) 是完全一样的。所以我们可以直接跳过后两个 \(AB\) 接着匹配；这也就证实了 \(next\) 数组的本质：最长公共前后缀的长度（注意：最长公共前后缀不可以是子串本身，否则我们的移动就没有意义了）.

我们可以用递推的方式来求解 \(next\) 数组，比如我们现在已经知道当前的公共前后缀了，接下来分两种情况讨论:

1. 下一个字符还是相同，直接构成了一个更长的公共前后缀；
2. 下一个字符不相同了，那我们就再次察看左边的前缀，与右面的后缀再次进行检查下一个字符是否相同，就可以得到下一个字符的 \(next\) 数组了！

那么这样我们的代码实现就很简单了:

                        
                          void buildnext(string t) {
	memset(ne, 0, sizeof ne);
	int len = 0; // 当前公共前后缀的长度
	int i = 1;
	while (i < t.size()) { // 依次生成每个next数值
		if (t[len] == t[i]) { // 下一个字符依然相同
			len++; // 长度+1
			ne[i] = len;
			i++;
		} else {
			if (len == 0) {
				ne[i] = 0; // 不存在直接为0
				i++;
			} else len = ne[len - 1]; // 是否存在更短的前后缀
		}
	}
}

                        
                      

最后放一下题和代码

                        
                          #include <bits/stdc++.h>
using namespace std;
int ne[100010];
void buildnext(string t) {
	memset(ne, 0, sizeof ne);
	int len = 0;
	int i = 1;
	while (i < t.size()) {
		if (t[len] == t[i]) {
			len++;
			ne[i] = len;
			i++;
		} else {
			if (len == 0) {
				ne[i] = 0;
				i++;
			} else len = ne[len - 1];
		}
	}
}
void kmp(string s, string t) {
	buildnext(t);
	int i = 0, j = 0;
	while (i < s.size()) {
		if (s[i] == t[j]) i++, j++;
		else if (j > 0) j = ne[j - 1];
		else i++;
		if (j == t.size()) cout << i - j << ' ';
	}
}
int main() {
	int n, m;
	string s, t;
	cin >> n >> t >> m >> s;
	kmp(s, t);
	return 0;
}

                        
                      

码字不易qwq 如果觉得这篇文章还不错的话，请点个赞吧！ 如果有任何问题，欢迎在评论区提问，我会尽可能的第一时间回复！ 。

最后此篇关于KMP字符串匹配算法的文章就讲到这里了,如果你想了解更多关于KMP字符串匹配算法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。