初识 BF 和 KMP 算法
我们先来看两段代码:
int BF()
{
auto pattern_size = pattern.size();
auto text_size = text.size();
auto pattern_index = 0;
auto text_index = 0;
while (pattern_index < pattern_size && text_index < text_size)
{
if (pattern[pattern_index] == text[text_index]) //匹配成功
{
++text_index;
++pattern_index;
}
else //匹配失败
{
text_index -= pattern_index - 1;
pattern_index = 0;
}
}
if (pattern_index == pattern_size) return text_index - pattern_index;
return -1;
}
int KMP()
{
auto pattern_size = pattern.size();
auto text_size = text.size();
auto pattern_index = 0;
auto text_index = 0;
while (pattern_index < pattern_size && text_index < text_size)
{
if (pattern_index == -1 || pattern[pattern_index] == text[text_index]) //匹配成功
{
++text_index;
++pattern_index;
}
else pattern_index = next[pattern_index]; //匹配失败
}
if (pattern_index == pattern_size) return text_index - pattern_index;
return -1;
}
上面的两段代码分别是BF 算法和MP(KMP)算法。
通过观察我们可以发现,这两段代码惊人的相似(假装是)。
我们通过模拟算法执行的过程来发现他们之间的关系吧。
BF 算法是朴素的匹配算法,其思想就是将文本串和模式串从头开始逐位匹配,若匹配失败(失配)则将模式串右移一位,再从头开始匹配。
上图共匹配了次。
可以发现,若在失配过多的情况下,BF 算法的效率能够非常高。
BF 算法中的、步都是无用的匹配,因为且,所以,第二步必然匹配失败,第四步同理。MP(KMP)算法就对此进行改进,不回溯文本串的下标,只改变模式串的下标,减去了这两步。
上图共匹配了次。
我们就得到了第一个结论:
MP(KMP)算法与BF 算法的区别在于BF 算法每次失配后模式串仅右移一位,而MP(KMP)算法将右移位。
计算右移位数
知道了MP(KMP)算法与BF 算法的区别后,现在的关键就是如何计算右移的值。
我们再看三个例子:
记为模式串所有前缀的集合,为模式串所有后缀的集合,对于样例一的已匹配串,。
可以发现,匹配串的 P 和 S 交集的最大元素为 AB,而前后两次匹配就是将模式串从前缀 AB 移动到后缀 AB。
因为MP(KMP)算法是从左向右遍历,我们只需记录模式串所有前缀子串的最长前缀后缀的长度为,那么每一次失配后,模式串右移位。记,MP(KMP)算法的主程序便出来了。
于是我们就得到了第二个结论:
MP 算法将右移的值大小等于已匹配模式串的最长前缀后缀。
计算 next 数组
那么如何计算呢?答案仍从MP(KMP)算法中来。
我们将模式串与自身进行匹配,注意到匹配成功的串就是对应子串的最长前缀后缀。
因此,我们只需在MP(KMP)算法的程序中匹配成功后增加对数组的赋值语句就完成了对数组的求解。(其中)
int GetNext()
{
next[0] = -1;
auto prefix = -1;
auto suffix = 0;
while (suffix < pattern_size - 1)
{
if (prefix == -1 || pattern[prefix] == pattern[suffix])
{
++prefix;
++suffix;
next[suffix] = next[prefix]; //赋值
}
else prefix = next[prefix];
}
}
至此,我们完成了MP 算法的所有实现。
第三个结论:
将模式串与自身匹配即可得到数组。
完成 KMP 算法
我们再来看一个例子:
在这个例子中,第二次匹配必然失败,因为,而,所以。
所以我们在函数中增加一次判断来优化算法。
int GetNext_KMP()
{
next[0] = -1;
auto prefix = -1;
auto suffix = 0;
while (suffix < pattern_size - 1)
{
if (prefix == -1 || pattern[prefix] == pattern[suffix])
{
++prefix;
++suffix;
if (pattern[prefix] != pattern[suffix]) next[suffix] = prefix;
else next[suffix] = next[prefix];
}
else prefix = next[prefix];
}
}
最终我们就得到了KMP 算法的所有代码。
时间复杂度
- BF 算法:
- MP 算法:
- KMP 算法:
- BF 算法:Brute Force 算法
- MP 算法:Morris-Pratt 算法
- KMP 算法:Knuth-Morris-Pratt 算法
- 参考代码