前言
KMP算法是Knuth、Morris、Pratt三人在BF算法的基础上同时提出的模式匹配的高效算法。本文以字符串匹配问题为例,以通俗易懂的语言对KMP算法进行逻辑分析、数学证明和代码实现。本文需要读者对BF算法有一定了解。阅读本文,读者能够清楚理解KMP算法的核心思想和代码逻辑,并自主实现该算法。
优化策略
在BF算法中,每次子串匹配失败后,i
指针(遍历主串)会回退到begin
位置的下一个位置,j
指针(遍历子串)会回退到子串的起始位置。假设主串的长度为M
,子串的长度为N
,同时回退i
指针和j
指针,时间复杂度为O(MN)
。如果字符串中重复字符较多,该算法就显得非常低效。
BF算法:
int BfSolution::BF(string str, string sub)
{
int StBegin = 0;
int SuBegin = 0;
int i = 0;//遍历主串
int j = 0;//遍历子串
while (i < str.length() && j < sub.length())
{
if (str.at(i) == sub.at(j)) {
i++;
j++;
}
else {
StBegin++;
i = StBegin;
j = SuBegin;
}
}
if (j == sub.length()) {
return StBegin;
}
else {
return -1;
}
}
KMP算法的优化策略为:匹配过程中i
不回退,j
回退到一个特定的位置,该位置不一定是起始位置,而需要做特定计算。
下面对j
回退的“特定的位置”做一个说明。需要注意的是,我们的目的是将主串和子串进行匹配,这个过程中i
不会回退,所以j
回退的位置应该为主串和子串已经尽量匹配的位置。例如下面两个字符串,两字符串在i
、j
位置匹配失败,若按照BF算法思想,则应将i
回退到StBegin
位置,将j
回退到起始位置,但是通过观察发现,
i
位置前面的a、b已经和子串的前两个a、b有了很大程度的匹配,所以我们大可以将j
回退到k
的位置,i
不回退,然后j
从k
位置继续向后判断和匹配。这里的k
位置即是我们需要的“特定的位置”。也就是说,我们需要找到j位置之前的真子串与i位置之前的真子串有最大程度匹配的位置。寻找该位置的过程,就是next
数组的计算过程。
next数组的计算
什么是next数组
上文说到,我们需要计算一个j
匹配失败后回退的位置,这个位置(下标)其实就是next
数组的一个元素。在实际匹配的过程中,每个位置都有可能匹配失败,所以我们需要针对子串的每个位置进行在该位置匹配失败后回退位置的计算,将计算的结果用一个一维数组维护,这个数组就是next数组。next数组记录了在各个位置匹配失败后j
应回退到的位置。
手动计算next数组
我们先尝试手动计算next
数组,在理解next
数组的基本计算方法后,再探讨next
数组计算中的规律,并用代码实现对next
数组的计算。在下文中继续以k
作为j
回退的位置,即next
数组的元素。
通过阅读上文你已经知道,计算next
数组其实就是要找到i
、j
位置之前的子串最大程度匹配的位置(k
)。在实际计算过程中,我们只考虑模式串(子串)的内容,所有的计算过程都是针对模式串(子串)的。
继续观察下面的字符串,i
和j
既然能够到达当前的位置,就说明i
之前和j
之前的字符串是完全匹配的,所以1
部分和3
部分一定相同,所以我们的问题就转化成了在A
位置之后、B
位置之前寻找两个相同的子串,这两个子串其中一个以0
位置开头,另一个子串以j - 1
位置结尾。不难发现,找到的两个子串的长度即为我们上文得到的位置。
由此我们得到计算k
的方法:寻找两个分别以0
位置开头,以j - 1
位置结尾的两个相同子串,这两个子串的长度即为 k
。
一个练习
计算下面模式串的next数组
答案:
需要注意的是,计算过程中两个子串必须严格遵循“分别以0
位置开头,以j - 1
位置结尾”,两子串重合的情况也包含在内。规定next[0] == -1。
next数组计算中的规律
为了下面的说明和证明方便,规定模式串为p
,从i
位置回退到的位置依然为k
。
如果我们知道next[i] = k
,那如何计算next[i + 1]
呢?
p[i] == p[k]时
通过上面的计算我们发现:当p[i] == p[k]
时,有next[i + 1] == k + 1
成立。例如上面练习中的字符串,当i == 4时,有k1==next[i] == 1,p[i] == 'b' ,p[k] == 'b',且k2==next[i + 1] == 2。
下面给出这个规律的数学证明。
数学证明
证明:当p[i] == p[k]
时,若p[i] == k
,则有p[i + 1] == k + 1
前提:next[i] == k
成立。为了下文表述方便,用p[x]~p[y]
表示从x位置到y位置的字符串。
假设next[i] == k
成立,则有p[0] ~ p[k - 1] == p[x] ~ p[i - 1]
,因为有两子串的长度相等,则有k - 1 - 0 == i - 1 - x
,得到x == i - k
,即
~
~
另外,由p[i] == p[k]
,可得
~
~
综上可得:
对比两式,当p[i] == p[k]
时,若p[i] == k
,则有p[i + 1] == k + 1
,得证。
p[i] != p[k]时
目前我们已经知道p[i] == p[k]
时next[i + 1]
的求法,当p[i] != p[k]
时又该当如何?
从逻辑角度思考上面得到的结论:当p[i] == p[k]
时,说明p[i]位置的字符可以归为前面已经匹配的子串,故当计算i + 1位置的k时,只需在原来k的基础上加1,表示在i + 1位置回退时只需回退到k的后一个位置即可。当p[i] != p[k]时,说明i + 1位置与之前已匹配的子串没有绝对的匹配关系,此时k应该继续回退,直到p[i] == p[k]
或k == -1
,然后根据p[i] == p[k]时的规律进行计算。
getNext()实现
有了上面的储备知识,我们就可以编写计算next数组的的代码。
/*
@param next next数组
@param sub 模式串
@param k 回退位置(next数组的数据)
@param i 遍历sub
*/
void KmpSolution::getNext(int*& next, string sub)
{
next[0] = -1;
int k = -1;//k一直是前一项(sub.at(i - 1))的k
for (int i = 1; i < sub.length(); )//注意这里i从 1 开始
{
//p[i] == p[k]
if (k == -1 || sub.at(i - 1) == sub.at(k)){
next[i] = k + 1;
k++;//这种情况k应该自增1
i++;
}
//p[i] != p[k]
else {
k = next[k];//继续回退
}
}
}
完整代码
void KmpSolution::getNext(int*& next, string sub)
{
next[0] = -1;
int k = -1;//k一直是前一项(sub.at(i - 1))的k
for (int i = 1; i < sub.length(); )
{
if (k == -1 || sub.at(i - 1) == sub.at(k)){
next[i] = k + 1;
k++;//这种情况k应该自增1
i++;
}
else {
k = next[k];
}
}
}
/*
@param str 主串
@param sub 模式串
@param i 遍历主串
@param j 遍历模式串
*/
int KmpSolution::KMP(string str, string sub)
{
int i = 0;
int j = 0;
int lenStr = str.length();
int lenSub = sub.length();
int* next = new int[lenSub];
getNext(next, sub);//计算next数组
while (i < lenStr && j < lenSub)
{
if (j == -1 || str.at(i) == sub.at(j)){
i++;
j++;
}
else {
j = next[j];
}
}
if (j == lenSub) {
return i - j;
}
else {
return -1;
}
}