挑战最通俗的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
如果当前的字母匹配,那就把两个指针都往后移一个字符。
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
最后放一下题和代码:
#include
using namespace std;
int ne[100010];
void buildnext(string t) {
memset(ne, 0, sizeof ne);
int len = 0;
int i = 1;
while (i 0) j = ne[j - 1];
else i++;
if (j == t.size()) cout > n >> t >> m >> s;
kmp(s, t);
return 0;
}
码字不易qwq
如果觉得这篇文章还不错的话,请点个赞吧!
如果有任何问题,欢迎在评论区提问,我会尽可能的第一时间回复!
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: k8s实战案例之部署redis单机和redis cluster
1、在k8s上部署redis单机 1.1、redis简介 redis是一款基于BSD协议,开源的非关系型数据库(nosql数据库),作者是意大利开发者Salvatore Sanfilippo在2009年发布,使用C语言编写;redis是基于内存存储,而且是目前…