Knuth–Morris–Pratt 算法

字符串匹配 ①

2 年前
140
1 min

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

上图共匹配了1313次。

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

MP

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

上图共匹配了1111次。

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

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

计算右移位数

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

我们再看三个例子:

example

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

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

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

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

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

计算 next 数组

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

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

self

因此,我们只需在MP(KMP)算法的程序中匹配成功后增加对nextnext数组的赋值语句就完成了对nextnext数组的求解。(其中next[0]=1,next[i]=0,i>0next[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 算法的所有实现。

第三个结论:

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

完成 KMP 算法

我们再来看一个例子:

KMP

在这个例子中,第二次匹配必然失败,因为pattern[i]=pattern[next[i]]pattern[i]=pattern[next[i]],而pattern[i]text[i]pattern[i] \neq text[i],所以pattern[next[i]]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)O(nm)
  • MP 算法:O(m)+O(n+m)O(m)+O(n+m)
  • KMP 算法:O(m)+O(n+m)O(m)+O(n+m)

  • BF 算法:Brute Force 算法
  • MP 算法:Morris-Pratt 算法
  • KMP 算法:Knuth-Morris-Pratt 算法
  • 参考代码
Last modified on 十一月 3日 2020 4:55:53 下午
使用 WSL 搭建开发环境
© 2020 · YXL
Build with Gatsby