KMP算法,俗称看毛片算法,顾名思义,以下是算法介绍:
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
例子
源字符串 src:aaabc 索引:i
模式子串 pat:aabc 索引:k
BF 算法
在匹配字串算法中,最符合人类直觉的当属BF算法,该算法将模式子串与源字符串逐字比较,一旦发现匹配失败,则将源字符串索引回溯以此循环。
匹配过程如下:
i = 0, k = 0; i = 1, k = 1, i = 2, k = 2
i = 1; k = 0; i = 2; k = 1; i = 3; k = 2; i = 4, k = 3
在 i = 2, k = 2 的时候,匹配失败,因此 i 回溯重新匹配,如果模式子串与源字符串连续相同的部分很多,则会发生多次回溯,白白浪费性能。
KMP 算法
kmp算法可以避免 i 回溯,并且让 k 根据模式子串的特征进行回溯。算法分两部分,第一部分计算next数组,该数组记录当匹配失败时,k 回溯到哪个位置。第二部分则结合next数组进行字符串匹配。
计算next数组
next数组是根据模式子串的特征来计算,结合上面的例子看:
aaa
bc i = 2
aab
c k = 2
匹配失败时,在 i 不回溯的情况下,只要让 k = 1 就可以让整个匹配继续往下执行。
该模式子串有一个特征,就是前两个字符串是一样的,也就是说,当 k = 2 匹配失败时,可以把整个字符串往后挪动,也不会影响后续匹配。
aaa
bc i=2
aa
bc k=1
因此,我们需要 k = 2,next[k] = 1。
计算next的思路:
k = -1, i = 1
next[0] = -1,第一个字符匹配失败,没有可回溯的位置。
当 pat[k + 1] = pat[i],则 k = k + 1,next[i++] = k
当 pat[k + 1] != pat[i] 且 k = -1,则 next[i++] = k
否则 k = next[k]
计算结果:
pat:a,a,b,c
next:-1,0,1,-1
源码
std::vector<size_t> GetNext(const std::string str)
{
auto i = (size_t)1;
auto k = SIZE_MAX;
std::vector<size_t> next(str.size(), SIZE_MAX);
while (i != str.size())
{
if (k == SIZE_MAX || str[k + 1] == str[i])
{
if (str[k + 1] == str[i])
++k;
next[i++] = k;
}
else
{
k = next[k];
}
}
return std::move(next);
}
子串匹配
这部分就简单多了,只要发生不匹配,就根据 next数组 回溯 k。
std::string KMPImpl(const std::string & src, const std::string & pat)
{
auto i = (size_t)0;
auto k = (size_t)0;
auto next = GetNext(pat);
while (i != src.size() && k != pat.size())
{
if (k != SIZE_MAX && src[i] == pat[k])
{
++i; ++k;
}
else if (k == SIZE_MAX && src[i] == pat[0])
{
++i; k = 1;
}
else if (k == SIZE_MAX && src[i] != pat[0])
{
++i; k = 0;
}
else
{
k = next[k];
}
}
return std::move(pat.size() == k? src.substr(i - k, k) : std::string());
}
inline std::string KMP(const std::string & src, const std::string & pat)
{
if (src.empty() || pat.empty() || pat.size() > src.size())
{
return std::string();
}
return KMPImpl(src, pat);
}
网友评论