Knuth–Morris–Pratt 算法

初识 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 算法是朴素的匹配算法，其思想就是将文本串和模式串从头开始逐位匹配，若匹配失败（失配）则将模式串右移一位，再从头开始匹配。

上图共匹配了$13$次。

可以发现，若在失配过多的情况下，BF 算法的效率能够非常高。

BF 算法中的$2$、$4$步都是无用的匹配，因为$pattern[0] = text[0]$且$text[0] \neq text[1]$，所以$pattern[0] \neq text[1]$，第二步必然匹配失败，第四步同理。MP(KMP)算法就对此进行改进，不回溯文本串的下标，只改变模式串的下标，减去了这两步。

上图共匹配了$11$次。

我们就得到了第一个结论：

MP(KMP)算法与BF 算法的区别在于BF 算法每次失配后模式串仅右移一位，而MP(KMP)算法将右移$k(k \geq 1, k \in N)$位。

计算右移位数

知道了MP(KMP)算法与BF 算法的区别后，现在的关键就是如何计算右移的$k$值。

我们再看三个例子：

记$P$为模式串所有前缀的集合，$S$为模式串所有后缀的集合，对于样例一的已匹配串$P=\{A,AB,ABC,ABCA,ABCAB\}$，$S=\{B,AB,CAB,BCAB,ABCAB\}$。

可以发现，匹配串的 P 和 S 交集的最大元素为 AB​，而前后两次匹配就是将模式串从前缀 AB​ 移动到后缀 AB​。

因为MP(KMP)算法是从左向右遍历，我们只需记录模式串所有前缀子串的最长前缀后缀的长度为$l[i]$，那么每一次失配后，模式串右移$Length-l[i-1]-1$位。记$next[i]=l[i]$，MP(KMP)算法的主程序便出来了。

于是我们就得到了第二个结论：

MP 算法将右移的$k$值大小等于已匹配模式串的最长前缀后缀。

计算 next 数组

那么如何计算$next[i]$呢？答案仍从MP(KMP)算法中来。

我们将模式串与自身进行匹配，注意到匹配成功的串就是对应子串的最长前缀后缀。

因此，我们只需在MP(KMP)算法的程序中匹配成功后增加对$next$数组的赋值语句就完成了对$next$数组的求解。（其中$next[0]=-1, next[i]=0, i > 0$）

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 算法的所有实现。

第三个结论：

将模式串与自身匹配即可得到$next$数组。

完成 KMP 算法

我们再来看一个例子：

在这个例子中，第二次匹配必然失败，因为$pattern[i]=pattern[next[i]]$，而$pattern[i] \neq text[i]$，所以$pattern[next[i]] \neq text[i]$。

所以我们在函数中增加一次判断来优化算法。

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 算法：$O(nm)$
• MP 算法：$O(m)+O(n+m)$
• KMP 算法：$O(m)+O(n+m)$

• BF 算法：Brute Force 算法
• MP 算法：Morris-Pratt 算法
• KMP 算法：Knuth-Morris-Pratt 算法
• 参考代码