挑战最通俗的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\) 数组，比如我们现在已经知道当前的公共前后缀了，接下来分两种情况讨论：

下一个字符还是相同，直接构成了一个更长的公共前后缀；
下一个字符不相同了，那我们就再次察看左边的前缀，与右面的后缀再次进行检查下一个字符是否相同，就可以得到下一个字符的 \(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
如果觉得这篇文章还不错的话，请点个赞吧！
如果有任何问题，欢迎在评论区提问，我会尽可能的第一时间回复！