美文网首页
算法 & 数据结构——KMP算法

算法 & 数据结构——KMP算法

作者: 落单的毛毛虫 | 来源:发表于2018-03-27 20:15 被阅读0次

    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数组是根据模式子串的特征来计算,结合上面的例子看:
    aaabc i = 2
    aab c k = 2
    匹配失败时,在 i 不回溯的情况下,只要让 k = 1 就可以让整个匹配继续往下执行。
    该模式子串有一个特征,就是前两个字符串是一样的,也就是说,当 k = 2 匹配失败时,可以把整个字符串往后挪动,也不会影响后续匹配。
    aabc i=2
     abc 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);
    }
    

    相关文章

      网友评论

          本文标题:算法 & 数据结构——KMP算法

          本文链接:https://www.haomeiwen.com/subject/pziscftx.html