侧边栏壁纸
  • 累计撰写 278 篇文章
  • 累计创建 3 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

【算法】KMP算法

xuanxuan
2021-04-28 / 0 评论 / 0 点赞 / 2 阅读 / 3982 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2024-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

@TOC


强烈推荐Carl老哥的视频!!!

多看几遍肯定是可以学会的。

理论篇——帮你把KMP算法学个通透!(理论篇)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

求Next数组代码篇——帮你把KMP算法学个通透!(求next数组代码篇)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili 欢迎访问我的小站——半生瓜のblog同步更新哦。


1.什么是KMP算法

​ KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。(百度百科)

2.KMP算法能解决哪些问题

解决字符串匹配问题

给出文本串和模式串,用两层for循环进行匹配,进行暴力匹配,时间复杂度是O(m,n).其中m是模式串长度,n是文本串长度。

3.KMP算法是如何运行的

给出两个要匹配的串,文本串和模式串。

在这里插入图片描述

第一次匹配

在这里插入图片描述

第二次匹配

在这里插入图片描述

跳到b处继续进行匹配

这就是KMP算法。

4.KMP算法是如何进行跳的

用到了很重要的表——前缀表。

那么,KMP算法为什么不用hash表或者其它表呢?


前缀表的特性:

  • 如何实现:当进行到不匹配的元素时,找到该元素前面的字串,找到一组相等的前后缀,在该前缀的后面进行第二次匹配,就跳过去了。其实就是找最长相等前后缀的长度,从这个以这个长度为下标的元素开始进行匹配。

  • 前缀:包括首元素不包括尾元素的所有字串,都称为前缀。

  • 后缀:包括尾元素不包括首元素的所有字串,都称为后缀。


5.如何求取前缀表

  • 求最长相等(公共)前后缀

    • a的最长相等(公共)前后缀是0

    aa的最长相等(公共)前后缀是1

    aab的最长相等(公共)前后缀是0

    ​ aaba的最长相等(公共)前后缀是1

    ​ aabaa的最长相等(公共)前后缀是2

    ​ aabaaf的最长相等(公共)前后缀是0

    所以得出此模式串的前缀表是010120

  • 得到最长相等(公共)前后缀是2

    • 2意味着:这里有一个后缀aa,前面有一个与其相等的前缀aa。
    • 在后缀(aa)的后面(是f)后面不匹配(冲突)了。
    • 就找与其相等的前缀(前面那个aa)后面那个元素(b)开始匹配。
    • (其实就是从最长相等前后缀的长度下标开始。)
    • (此模式串最长相等前后缀是2,就从该模式串下标为2的元素开始匹配。)
    • (2表示的是最长相等前后缀的长度,我们要跳到前缀的后面,前缀的后面的下标正好是前缀的长度,因为串的下标是从0开始的。)
  • 匹配成功,完成匹配过程。


流程图:

在这里插入图片描述


6.KMP算法的实现

有的做法会将前缀表进行一些调整,但总的思想是相同的。

有的用next数组,有的用perfix,这里用的Next数组。

碰到了冲突的位置,我们要向前回退,这是Next数组的核心所在。

对于实现,不同的人有不同的方法。

这里就用前缀表作为我们的Next数组。

求出来的Next数组就是该模式串的前缀表。

那么具体的代码应该怎么写呢?


明确求Next数组有几个步骤 1.初始化 2.处理前后缀不同的情况 3.处理前后缀不相同的情况 4.更新Next数组的值


j指向前缀末尾位置(还代表着i之前包括i,字串的最长相等前后缀的长度)

i指向后缀末尾位置。


void getNext(int* next,const string&S)//S为模式串,(此代码类似于伪代码)
{ 
    //1.初始化
    int j = 0;//j初始化为0,前缀一开始是从开始的位置开始。
    next[0];//next数组初始位置也是0。
    //初始化完成
    //i的初始化就进入到我们的循环遍历里了
    //因为要比较前后缀所对应的字符是否相等,那i就应该是从1开始,这样i和j才能进行比较
    for(int i = 1;i<S.size;i++)
    {
        //2.处理前后缀不相同情况
        //遇到不匹配看前一位 
        //这里的while容易写成if,我们回退的过程并不是一步就完事的
        //要判断前一位所以j>0 
        //否则产生负数会造成数组越界
        while(j > 0 && S[i] != S[j])
        {
            j = next[j-1];
        }
        //3.处理前后缀相同的情况
        //这时候j应该+1,因为j不仅代表着前缀末尾的位置,还代表着i以及i之前这个字串的最长相等前后缀的长度。
        if(S[i] == S[j])
        {
            j++;        
        }
        //更新Next数组
        next[i] = j;
        //在循环里面,i++,向后面走一位
    }
}
0

评论区