kmp算法_kmp算法详解 - CSDN
kmp算法 订阅
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]  。 展开全文
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]  。
信息
时间复杂度
O(m+n) [1]
外文名
The Knuth-Morris-Pratt Algorithm [1]
发现者
D.E.Knuth等 [1]
中文名
KMP算法 [1]
算法基础
Brute-Force [2]
应    用
字符串匹配 [1]
kmp算法简介
KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率 [2]  。
收起全文
  • KMP算法——很详细的讲解

    万次阅读 多人点赞 2018-09-09 10:56:56
    KMP算法(研究总结,字符串) KMP算法(研究总结,字符串) 前段时间学习KMP算法,感觉有些复杂,不过好歹是弄懂啦,简单地记录一下,方便以后自己回忆。 引入 首先我们来看一个例子,现在有两个字符串A和B,...
    原文地址:http://www.cnblogs.com/SYCstudio/p/7194315.html 
    

    KMP算法(研究总结,字符串)

    KMP算法(研究总结,字符串)

    前段时间学习KMP算法,感觉有些复杂,不过好歹是弄懂啦,简单地记录一下,方便以后自己回忆。

    引入

    首先我们来看一个例子,现在有两个字符串A和B,问你在A中是否有B,有几个?为了方便叙述,我们先给定两个字符串的值
    A=”abcaabababaa”
    B=”abab”

    那么普通的匹配是怎么操作的呢?
    当然就是一位一位地比啦。(下面用蓝色表示已经匹配,黑色表示匹配失败)
    此处输入图片的描述
    但是我们发现这样匹配很浪费!
    为什么这么说呢,我们看到第4步:
    此处输入图片的描述
    在第4步的时候,我们发现第3位上c与a不匹配,然后第五步的时候我们把B串向后移一位,再从第一个开始匹配。
    此处输入图片的描述
    这里就有一个对已知信息很大的浪费,因为根据前面的匹配结果,我们知道B串的前两位是ab,所以不管怎么移,都是不能和b匹配的,所以应该直接跳过对A串第二位的匹配,对于A串的第三位也是同理。

    或许这这个例子还不够经典,我们再举一个。

    A=”abbaabbbabaa”
    B=”abbaaba”

    在这个例子中,我们依然从第1位开始匹配,直到匹配失败:

    abbaab
    bbabba
    abbaaba
    我们发现第7位不匹配
    那么我们若按照原来的方式继续匹配,则是把B串向后移一位,重新从第一个字符开始匹配
    abbaabbbabba
    _abbaaba
    依然不匹配,那我们就要继续往后移咯。
    且住!
    既然我们已经匹配了前面的6位,那么我们也就知道了A串这6位和B串的前6位是匹配的,我们能否利用这个信息来优化我们的匹配呢?
    也就是说,我们能不能在上面匹配失败后直接跳到:
    abbaabbbabba
    ____abbaaba
    这样就可以省去很多不必要的匹配。

    KMP算法

    KMP算法就是解决上面的问题的,在讲述之前,我们先摆出两个概念:

    前缀:指的是字符串的子串中从原串最前面开始的子串,如abcdef的前缀有:a,ab,abc,abcd,abcde
    后缀:指的是字符串的子串中在原串结尾处结尾的子串,如abcdef的后缀有:f,ef,def,cdef,bcdef

    KMP算法引入了一个F数组(在很多文章中会称为next,但笔者更习惯用F,这更方便表达),F[i]表示的是前i的字符组成的这个子串最长的相同前缀后缀的长度!
    怎么理解呢?
    例如字符串aababaaba的相同前缀后缀有a和aaba,那么其中最长的就是aaba。

    KMP算法的难理解之处与本文叙述的约定

    在继续我们的讲述之前,笔者首先讲一下为什么KMP算法不是很好理解。
    虽然说网上关于KMP算法的博客、教程很多,但笔者查阅很多资料,详细讲述过程及原理的不多,真正讲得好的文章在定义方面又有细微的不同(当然,真正写得好的文章也有,这里就不一一列举),比如说有些从1开始标号,有些next表示的是前一个而有些是当前的,通读下来,难免会混乱。
    那么,为了防止读者在接下来的内容中感到和笔者之前学习时同样的困惑,在这里先对下文做一些说明和约定。

    1.本文中,所有的字符串从0开始编号
    2.本文中,F数组(即其他文章中的next),F[i]表示0~i的字符串的最长相同前缀后缀的长度。

    F数组的运用

    那么现在假设我们已经得到了F的所有值,我们如何利用F数组求解呢?
    我们还是先给出一个例子(笔者用了好长时间才构造出这一个比较典型的例子啊):
    A=”abaabaabbabaaabaabbabaab”
    B=”abaabbabaab”

    当然读者可以通过手动模拟得出只有一个地方匹配
    abaabaabbabaaabaabbabaab
    那么我们根据手动模拟,同样可以计算出各个F的值

    B=”a b a a b b a b a a b “
    F= 0 0 1 1 2 0 1 2 3 4 5(2017.7.25 Update 这里之前有一个错误,感谢@ 歌古道指正)(2017.7.29 Update 好吧,这里原来还有一个错误,已经更正啦感谢@iwangtst)

    我们再用i表示当前A串要匹配的位置(即还未匹配),j表示当前B串匹配的位置(同样也是还未匹配),补充一下,若i>0则说明i-1是已经匹配的啦(j同理)。
    首先我们还是从0开始匹配:
    此处输入图片的描述
    此时,我们发现,A的第5位和B的第5位不匹配(注意从0开始编号),此时i=5,j=5,那么我们看F[j-1]的值:

    F[5-1]=2;

    这说明我们接下来的匹配只要从B串第2位开始(也就是第3个字符)匹配,因为前两位已经是匹配的啦,具体请看图:
    此处输入图片的描述
    然后再接着匹配:
    此处输入图片的描述
    我们又发现,A串的第13位和B串的第10位不匹配,此时i=13,j=10,那么我们看F[j-1]的值:

    F[10-1]=4

    这说明B串的0~3位是与当前(i-4)~(i-1)是匹配的,我们就不需要重新再匹配这部分了,把B串向后移,从B串的第4位开始匹配:
    此处输入图片的描述

    这时我们发现A串的第13位和B串的第4位依然不匹配
    此处输入图片的描述
    此时i=13,j=4,那么我们看F[j-1]的值:

    F[4-1]=1

    这说明B串的第0位是与当前i-1位匹配的,所以我们直接从B串的第1位继续匹配:
    此处输入图片的描述
    但此时B串的第1位与A串的第13位依然不匹配
    此处输入图片的描述
    此时,i=13,j=1,所以我们看一看F[j-1]的值:

    F[1-1]=0

    好吧,这说明已经没有相同的前后缀了,直接把B串向后移一位,直到发现B串的第0位与A串的第i位可以匹配(在这个例子中,i=13)
    此处输入图片的描述
    再重复上面的匹配过程,我们发现,匹配成功了!
    此处输入图片的描述

    这就是KMP算法的过程。
    另外强调一点,当我们将B串向后移的过程其实就是i++,而当我们不动B,而是匹配的时候,就是i++,j++,这在后面的代码中会出现,这里先做一个说明。

    最后来一个完整版的(话说做这些图做了好久啊!!!!):
    此处输入图片的描述

    F数组的求解

    既然已经用这么多篇幅具体阐述了如何利用F数组求解,那么如何计算出F数组呢?总不能暴力求解吧。

    KMP的另外一个巧妙的地方也就在这里,它利用我们上面用B匹配A的方法来计算F数组,简单点来说,就是用B串匹配B串自己!
    当然,因为B串==B串,所以如果直接按上面的匹配,那是毫无意义的(自己当然可以完全匹配自己啦),所以这里要变一变。

    因为上面已经讲过一部分了,先给出计算F的代码:

    for (int i=1;i<m;i++)
    {
        int j=F[i-1];
        while ((B[j+1]!=B[i])&&(j>=0))
            j=F[j];
        if (B[j+1]==B[i])
            F[i]=j+1;
        else
            F[i]=-1;
    }

    首先可以确定的几点是:

    1.F[0]=-1 (虽说这里应该是0,但为了方便判越界,同时为了方便判断第0位与第i位,程序中这里置为-1)
    2.这是一个从前往后的线性推导,所以在计算F[i]时可以保证F[0]~F[i-1]都是已经计算出来的了
    3.若以某一位结尾的子串不存在相同的前缀和后缀,这个位的F置为-1(这里置为-1的原因同第一条一样)

    重要!:另外,为了在程序中表示方便,在接下来的说明中,F[i]=0表示最长相同前缀后缀长度为1,即真实的最长相同前缀后缀=F[i]+1。(重要的内容要放大)
    为什么要这样设置呢,因为这时F[i]代表的就不仅仅与前后缀长度有关了,它还代表着这个前缀的最后一个字符在子串B中的位置。

    所以,之前上面列出的F值要变一下(这里用’_’辅助对齐):

    B=”a _b a a b _b a b a a b “
    F= -1 -1 0 0 1 -1 0 1 2 3 4

    那么,我们同样可以推出,求解F的思路是:看F[i-1]这个最长相同前缀后缀的后面是否可以接i,若可以,则直接接上,若不可以,下面再说。
    举个例子:
    还是以B=”abaabbabaab”为例,我们看到第2个。

    B=”a b a a b b a b a a b”
    F=-1 -1

    此时这个a的前一个b的F值为-1,所以此时a不能接在b的后面(b的相同最长前缀后缀是0啊),此时,j=-1,所以我们判断B[j+1]与B[2],即B[0]与B[2]是否一样。一样,所以F[2]=j+1=0(代表前0~2字符的最长相同前缀后缀的前缀结束处是B[0],长度为0+1=1)。

    再来看到第3个:

    B=”a b a a b b a b a a b”
    F=-1 -1 0

    开始时,j=F[3-1]=0,我们发现B[j+1=1]!=B[i=3],所以j=F[j]=-1,此时B[j+1=0]==B[i=3],所以F[3]=j+1=0。

    最后举个例子,看到第4个

    B=”a b a a b b a b a a b”
    F=-1 -1 0 0

    j首先为F[4-1]=0,我们看到B[j+1=1]==B[i],所以F[i]=j+1=1。

    后面的就请读者自己慢慢推导了。再强调一遍,我们这样求出来的F值是该最长相同前缀后缀中的前缀的结束字符的数组位置(从0开始编号),如果要求最长相同前缀后缀的长度,要输出F[i]+1。

    代码

    求解F数组:

    for (int i=1;i<m;i++)
    {
        int j=F[i-1];
        while ((B[j+1]!=B[i])&&(j>=0))
            j=F[j];
        if (B[j+1]==B[i])
            F[i]=j+1;
        else
            F[i]=-1;
    }

    利用F数组寻找匹配,这里我们是每找到一个匹配就输出其开始的位置:

    while (i<n)
    {
        if (A[i]==B[j])
        {
            i++;
            j++;
            if (j==m)
            {
                printf("%d\n",i-m+1);//注意,这里输出的位置是从1开始标号的,如果你要输出从0开始标号的位置,应该是是i-m.这份代码是我做一道题时写的,那道题要求输出的字符串位置从1开始标号.感谢@Draymonder指出了这个疏漏,更多内容请看评论区
                j=F[j-1]+1;
            }
        }
        else
        {
            if (j==0)
                i++;
            else
                j=F[j-1]+1;
        }
    }
    展开全文
  • kmp算法(最简单最直观的理解,看完包会)

    千次阅读 多人点赞 2018-09-07 20:31:18
    本文将以特殊的方式来让人们更好地理解kmp算法,不包括kmp算法的推导,接下来,我们将从朴素算法出发。 在这之前,我们先设主串为S,模式串为T,我们要解决的询问是主串中是否包含模式串(即T是否为S的字串)。 版权...

    本文将以特殊的方式来让人们更好地理解kmp算法,不包括kmp算法的推导,接下来,我们将从朴素算法出发。
    在这之前,我们先设主串为S,模式串为T,我们要解决的询问是主串中是否包含模式串(即T是否为S的子串)。
    版权声明:本文为原创文章,转载请标明出处。

    朴素算法

    朴素算法说白了就是暴力,简单地讲就是先从主串的第一个位置开始逐个对模式串进行匹配,若匹配失败,则从主串的第二个位置继续进行匹配,以此类推,直到匹配成功或主串的结尾。
    举个例子1
    主串S:aabaaced
    模式串T:aac
    首先我们会进行这样的匹配
    aabaaced
    aac
    发现T[0]和S[0]匹配,T[1]和S[1]匹配,而T[2]==c和S[2]==b匹配失败,接着我们会这样
    aabaaced
      aac
    发现T[1]和S[1]匹配,而T[2]==c和S[3]==b匹配失败,接着
    aabaaced
        aac
    发现T[2]和S[2]不匹配,继续
    aabaaced
          aac
    这次终于成功匹配。
    以上所述就是朴素算法,然而我们再来看一个例子
    举个例子2
    主串S:aaaaaaaaaaaaaaaaaaaaab
    模式串T:aaaaab
    如果这个例子我们还用朴素算法去匹配,很显而易见,每次我们都要从头开始匹配,做法如下
    aaaaaaaaaaaaaaaaaaaaab
    aaaaab
    从T[0]到T[5],对S[0]和S[5]依次进行匹配,发现末尾(T[5]和S[5])没有匹配,继续
    aaaaaaaaaaaaaaaaaaaaab
      aaaaab
    从T[0]到T[5],对S[1]和S[6]依次进行匹配,发现末尾(T[5]和S[6])没有匹配,继续
    ……(此处省略大量的中间过程)
    aaaaaaaaaaaaaaaaaaaaab
                                 aaaaab
    终于匹配成功。
    如果用kmp算法,则过程如下:
    aaaaaaaaaaaaaaaaaaaaab
    aaaaab
    从T[0]到T[5],对S[0]和S[5]依次进行匹配,发现末尾(T[5]和S[5])没有匹配,继续
    aaaaaaaaaaaaaaaaaaaaab
      aaaaab
    直接匹配T[5]和S[6]发现匹配失败,继续
    ……(此处省略大量的中间过程)
    aaaaaaaaaaaaaaaaaaaaab
                                      aaaaab
    我们发现kmp算法从第二次匹配开始省略了T[0]到T[4]对S的匹配,因为由kmp算法我们知道T[0]到T[4]一定已经匹配了,不需要再判断,那么kmp算法是怎么知道并利用这些信息的呢,
    接下来我们进入正题。

    kmp算法的理解

    首先我们从朴素算法出发,一步一步去引出kmp算法
    主串S:S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
    模式串T:T[1]T[2]T[3]T[4]T[5]T[6]
    一开始,我们先用朴素算法进行匹配,得到
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
    T[1]T[2]T[3]T[4]T[5]T[6]
    这时候,我们假设前四个匹配成功了,然而S[5]与T[5]匹配失败,即有
    T[1]==S[1]
    T[2]==S[2]
    T[3]==S[3]
    T[4]==S[4]
    T[5]!=S[5]
    按照朴素算法的做法,我们应该把T串往右移,得到这样的式子进行匹配
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
          T[1]T[2]T[3]T[4]T[5]T[6]
    但是这时候我们思考这样一个问题,将模式串右移一位是否有可能成功匹配??
    显而易见,这样匹配成功的充要条件是:
    T[1]==S[2]
    T[2]==S[3]
    T[3]==S[4]
    T[4]==S[5]
    T[5]==S[6]
    T[6]==S[7]
    结合上次匹配的结果,我们可以把这次匹配成功的充要条件进行变化:
    T[1]==S[2]==T[2]
    T[2]==S[3]==T[3]
    T[3]==S[4]==T[4]
    T[4]==S[5]
    T[5]==S[6]
    T[6]==S[7]
    由此我们可以得出一个上次匹配失败后将模式串T右移一位能够匹配成功的充要条件:
    T[1]==T[2]
    T[2]==T[3]
    T[3]==T[4]
    T[4]==S[5]
    T[5]==S[6]
    T[6]==S[7]
    进而得到上次匹配失败后将模式串T右移一位能够过匹配成功的必要条件:
    T[1]==T[2]
    T[2]==T[3]
    T[3]==T[4]
    注意,这个必要条件只和模式串T有关!
    接着我们讨论将模式串右移两位是否能匹配成功:
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
                 T[1]T[2]T[3]T[4]T[5]T[6]
    显而易见,这样匹配成功的充要条件是:
    T[1]==S[3]
    T[2]==S[4]
    T[3]==S[5]
    T[4]==S[6]
    T[5]==S[7]
    T[6]==S[8]
    结合上次匹配的结果,我们可以把这次匹配成功的充要条件进行变化:
    T[1]==S[3]==T[3]
    T[2]==S[4]==T[4]
    T[3]==S[5]
    T[4]==S[6]
    T[5]==S[7]
    T[6]==S[8]
    进而得到上次匹配失败后将模式串T右移两位能够过匹配成功的必要条件:
    T[1]==T[3]
    T[2]==T[4]
    注意,这个必要条件只和模式串T有关!
    最后我们讨论将模式串右移三位是否能匹配成功:
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
                       T[1]T[2]T[3]T[4]T[5]T[6]
    显而易见,这样匹配成功的充要条件是:
    T[1]==S[4]
    T[2]==S[5]
    T[3]==S[6]
    T[4]==S[7]
    T[5]==S[8]
    T[6]==S[9]
    结合上次匹配的结果,我们可以把这次匹配成功的充要条件进行变化:
    T[1]==S[4]==T[4]
    T[2]==S[5]
    T[3]==S[6]
    T[4]==S[7]
    T[5]==S[8]
    T[6]==S[9]
    进而得到上次匹配失败后将模式串T右移三位能够过匹配成功的必要条件:
    T[1]==T[4]
    上面讨论了三种情况,在第一次匹配到T[5]的时候匹配失败了,将模式串分别右移动一位,右移动两位,右移动三位
    是否有可能成功
    我们这里设Q为T[1]T[2]T[3]T[4]
    可以发现:
    右移动一位成功的必要条件是T[1]==T[2],T[2]==T[3],T[3]==T[4],即Q的三个前缀等于三个后缀(T[1]T[2]T[3]==T[2]T[3]T[4])

    右移动两位成功的必要条件是T[1]==T[3],T[2]==T[4],即Q的两个前缀等于两个后缀!(T[1]T[2]==T[3]T[4])

    右移动三位成功的必要条件是T[1]==T[4],即Q的一个前缀等于一个后缀!
    注意,这些移动都只和模式串有关!
    这时候,我们可以得出一个结论:
    上面这个例子,T[5]是匹配失败的位置,我们把匹配失败的位置的前面的所有字符看作一个新的串Q,想要知道右移几位有可能匹配成功,我们需要讨论T[5]前面的字符组成的串Q,如果不满足Q的三个前缀等于三个后缀,我们可以直接跳过右移一位的情况,如果不满足Q的两个前缀等于两个后缀,我们可以直接跳过右移两位的情况,等等,而且,如果一旦满足,我们在右移后,不需要从模式串的头部开始匹配,因为如果满足,前面几个就已经匹配好了。就比如上面这个例子,若满足:
    T[1]==T[2]
    T[2]==T[3]
    T[3]==T[4]
    我们可以得到右移一位有可能匹配成功,而且因为有上次匹配失败后留下的信息
    T[2]==S[2]
    T[3]==S[3]
    T[4]==S[4]
    我们可以直接得到
    T[1]==T[2]==S[2]
    T[2]==T[3]==S[3]
    T[3]==T[4]==S[4]
    所以直接匹配T[4]和S[5]即可,这么一来,就是固定主串不动,从匹配失败的位置开始,判断模式串需要右移几位,然后从匹配失败的位置开始匹配即可,上面那个例子就是T[5]与S[5]匹配失败,由T[1]T[2]T[3]==T[2]T[3]T[4]可知接下来需要模式串右移一位并匹配T[4]和S[5]。

    kmp算法的使用

    在实际使用中,我们不可能匹配失败一次就去判断失败字符前面所有字符组成的串的最长相等的前缀和后缀,这样时间复杂度会很高,所以我们需要在匹配之前对模式串进行预处理,对每个字符如果匹配失败,要右移几位进行保存,在匹配中一旦失败,直接跳到那个位置就可以了,我们用next数组进行保存,比如上面的那个例子,T[5]匹配失败了,这时候就要让模式串的指针指向next[5],next[5]是我们在匹配之前就已经预处理过的。
    至于如何处理,本文不给予证明,靠下面的几串代码可以实现,读者自行思考或阅读书籍或其它文章即可。
    获得next数组的代码如下,T为模式串:

    void get_next() {
        next[0] = -1;
        int i = 0, j = -1;
        int len = strlen(T);
        while(i < len) {
            if(j == -1 || T[i] == T[j])
                next[++i] = ++j;
             else
                j = next[j];
        }
    }

    代码很短,其中next[i]代表的是如果在i位置匹配失败,应该从哪个位置继续匹配,跟i前面所有字符组成的串Q的前缀与后缀有关。注意,这个next数组是kmp算法的核心。
    接下来给出匹配的过程代码:

    bool KMP() {
        get_next();
        int len1 = strlen(T);
        int len2 = strlen(S);
        int i = 0, j = 0;           //i指向模式串T,j指向主串S
        while(j < len2) {
            if(T[i] == S[j]) {
                i++;
                j++;
                if(i == len1) {
                    return true;
                }
            } else {
                i = next[i];
                if(i == -1) {
                    j++;i++;
                }
            }
        }
        return false;
    }

    kmp算法的练习建议

    理解kmp算法:poj2752 poj2406 poj1961
    常规kmp算法练习:poj3461 poj2185

    如有错误或不妥之处,欢迎指正~

    展开全文
  • KMP算法—终于全部弄懂了

    万次阅读 多人点赞 2019-03-22 21:00:45
    详细讲解KMP算法,并对难点 k=next[k] 这条语句重点描述

    简介

      KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

    提取加速匹配的信息

      上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的,那么,它是则呢样来消除回溯的呢?就是因为它提取并运用了加速匹配的信息!
      这种信息就是对于每模式串 t 的每个元素 t j,都存在一个实数 k ,使得模式串 t 开头的 k 个字符(t 0 t 1…t k-1)依次与 t j 前面的 k(t j-k t j-k+1…t j-1这里第一个字符 t j-k 最多从 t 1 开始,所以 k < j)个字符相同。如果这样的 k 有多个,则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息,采用 next 数组表示,即 next[ j ]=MAX{ k }。

      
      加速信息,即数组 next 的提取是整个 KMP 算法中最核心的部分,弄懂了 next 的求解方法,也就弄懂了 KMP 算法的十之七八了,但是不巧的是这部分代码恰恰是最不容易弄懂的……
      
    先上代码

    void Getnext(int next[],String t)
    {
       int j=0,k=-1;
       next[0]=-1;
       while(j<t.length-1)
       {
          if(k == -1 || t[j] == t[k])
          {
             j++;k++;
             next[j] = k;
          }
          else k = next[k];//此语句是这段代码最反人类的地方,如果你一下子就能看懂,那么请允许我称呼你一声大神!
       }
    }
    

    ok,下面咱们分三种情况来讲 next 的求解过程

    1. 特殊情况
      当 j 的值为 0 或 1 的时候,它们的 k 值都为 0,即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便,我们将 next[0] 的值设置成 -1。

    2. 当 t[j] == t[k] 的情况
      举个栗子
      在这里插入图片描述
      观察上图可知,当 t[j] == t[k] 时,必然有"t[0]…t[k-1]" == " t[j-k]…t[j-1]",此时的 k 即是相同子串的长度。因为有"t[0]…t[k-1]" == " t[j-k]…t[j-1]",且 t[j] == t[k],则有"t[0]…t[k]" == " t[j-k]…t[j]",这样也就得出了next[j+1]=k+1。

    3. 当t[j] != t[k] 的情况
      关于这种情况,在代码中的描述就是“简单”的一句 k = next[k];。我当时看了之后,感觉有点蒙,于是就去翻《数据结构教程》。但是这本书里,对于这行代码的解释只有三个字:k 回退…!于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态,我心想,k 回退?我当然知道这是 k 退回,但是它为什么要会退到 next[k] 的位置?为什么不是回退到k-1???巴拉巴拉巴拉…此处省略一万字。

      我绞尽脑汁,仍是不得其解。于是我就去问度娘…
      在我看了众多博客之后,终于有了一种拨云见日的感觉,看下图
      在这里插入图片描述
         由第2中情况可知,当 t[j] == t[k] 时,t[j+1] 的最大子串的长度为 k,即 next[j+1] = k+1。但是此时t[j] != t[k] 了,所以就有 next[j+1] < k,那么求 next[j+1] 就等同于求 t[j] 往前小于 k 个的字符(包括t[j],看上图蓝色框框)与 t[k] 前面的字符(绿色框框)的最长重合串,即 t[j-k+1] ~ t[j] 与 t[0] ~ t[k-1] 的最长重合串(这里所说“最长重合串”实不严谨,但你知道是符合 k 的子串就行…),那么就相当于求 next[k](只不过 t[k] 变成了 t[j],但是 next[k] 的值与 t[k] 无关)!!!。所以才有了这句 k = next[k],如果新的一轮循环(这时 k = next[k] ,j 不变)中 t[j] 依然不等于 t[k] ,则说明倒数第二大 t[0~next[k]-1] 也不行,那么 k 会继续被 next[k] 赋值(这就是所谓的 k 回退…),直到找到符合重合的子串或者 k == -1。

    至此,算是把求解数组 next 的算法弄清楚了(其实是,终于把 k = next[k] 弄懂了…)

    因为这个算法神奇难解之处就在k=next[k]这一处的理解上,网上解析的非常之多,有的就是例证,举例子按代码走流程,走出结果了,跟肉眼看的一致,就认为解释了为什么k=next[k];很少有看到解释的非常清楚的,或者有,但我没有仔细和耐心看下去。我一般扫一眼,就大概知道这个解析是否能说的通。仔细想了三天,搞的千转百折,山重水复,一头雾气缭绕的。搞懂以后又觉得确实简单,但是绕人,烧脑。

    再此特别感谢昵称为“sofu6”的博客园主,正是他的博客,让我这愚笨的脑袋瓜开窍了

    KMP算法实现

    当你求出了 next 数组之后,KMP 算法就很轻易搞定了,下面我用三张图,让你明白 KMP 算法完成匹配的整个过程。
    以目标串:s,指针为 i ;模式串:t 指针为 j ; 为例
    在这里插入图片描述
    上图表示:“si-j ~ si-1” == “t 0 ~ t j-1”,s i != t j(前面都相等,但比较到 t j 时发现不相等了)且next[j] == k。
    在这里插入图片描述
    根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”,所以 “t 0 ~ t k-1” == “si-k ~ si-1
    在这里插入图片描述
    将模式串右移,得到上图,这样就避免了目标穿的指针回溯。

    都明了之后就可以手写 KMP 的代码了

    int KMP(String s,String t)
    {
       int next[MaxSize],i=0;j=0;
       Getnext(t,next);
       while(i<s.length&&j<t.length)
       {
          if(j==-1 || s[i]==t[j])
          {
             i++;
             j++;
          }
          else j=next[j];               //j回退。。。
       }
       if(j>=t.length)
           return (i-t.length);         //匹配成功,返回子串的位置
       else
          return (-1);                  //没找到
    }
    

    改进后的 next 求解方法

    先来看一下上面算法存在的缺陷:
    在这里插入图片描述
    显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]

    所以下一步我们应该是把j移动到第1个元素咯:
    在这里插入图片描述
    不难发现,这一步是完全没有意义的。因为后面的B已经不匹配了,那前面的B也一定是不匹配的,同样的情况其实还发生在第2个元素A上。

    显然,发生问题的原因在于t[j] == t[next[j]]。

    所以我们需要谈价一个判断:

    void Getnext(int next[],String t)
    {
       int j=0,k=-1;
       next[0]=-1;
       while(j<t.length-1)
       {
          if(k == -1 || t[j] == t[k])
          {
             j++;k++;
             if(t[j]==t[k])//当两个字符相同时,就跳过
                next[j] = next[k];
             else
                next[j] = k;
          }
          else k = next[k];
       }
    }
    

    本文对sofu6的博客多有借鉴,所以在此特别鸣谢,并附上他的博客:想看点这里

    展开全文
  • KMP算法最浅显理解——一看就明白

    万次阅读 多人点赞 2018-04-03 16:21:46
    KMP算法看懂了觉得特别简单,思路很简单,看不懂之前,查各种资料,看的稀里糊涂,即使网上最简单的解释,依然看的稀里糊涂。 我花了半天时间,争取用最短的篇幅大致搞明白这玩意到底是啥。 这里不扯概念,只讲...

    说明

    KMP算法看懂了觉得特别简单,思路很简单,看不懂之前,查各种资料,看的稀里糊涂,即使网上最简单的解释,依然看的稀里糊涂。
    我花了半天时间,争取用最短的篇幅大致搞明白这玩意到底是啥。
    这里不扯概念,只讲算法过程和代码理解:

    KMP算法求解什么类型问题

    字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。
    如下面两个字符串:

    char *str = "bacbababadababacambabacaddababacasdsd";
    char *ptr = "ababaca";

    str有两处包含ptr
    分别在str的下标10,26处包含ptr。

    “bacbababadababacambabacaddababacasdsd”;\
    这里写图片描述

    问题类型很简单,下面直接介绍算法

    算法说明

    一般匹配字符串时,我们从目标字符串str(假设长度为n)的第一个下标选取和ptr长度(长度为m)一样的子字符串进行比较,如果一样,就返回开始处的下标值,不一样,选取str下一个下标,同样选取长度为n的字符串进行比较,直到str的末尾(实际比较时,下标移动到n-m)。这样的时间复杂度是O(n*m)

    KMP算法:可以实现复杂度为O(m+n)

    为何简化了时间复杂度:
    充分利用了目标字符串ptr的性质(比如里面部分字符串的重复性,即使不存在重复字段,在比较时,实现最大的移动量)。
    上面理不理解无所谓,我说的其实也没有深刻剖析里面的内部原因。

    考察目标字符串ptr
    ababaca
    这里我们要计算一个长度为m的转移函数next。

    next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。

    比如:abcjkdabc,那么这个数组的最长前缀和最长后缀相同必然是abc。
    cbcbc,最长前缀和最长后缀相同是cbc。
    abcbc,最长前缀和最长后缀相同是不存在的。

    **注意最长前缀:是说以第一个字符开始,但是不包含最后一个字符。
    比如aaaa相同的最长前缀和最长后缀是aaa。**
    对于目标字符串ptr,ababaca,长度是7,所以next[0],next[1],next[2],next[3],next[4],next[5],next[6]分别计算的是
    aababaababababaababacababaca的相同的最长前缀和最长后缀的长度。由于aababaababababaababacababaca的相同的最长前缀和最长后缀是“”,“”,“a”,“ab”,“aba”,“”,“a”,所以next数组的值是[-1,-1,0,1,2,-1,0],这里-1表示不存在,0表示存在长度为1,2表示存在长度为3。这是为了和代码相对应。

    下图中的1,2,3,4是一样的。1-2之间的和3-4之间的也是一样的,我们发现A和B不一样;之前的算法是我把下面的字符串往前移动一个距离,重新从头开始比较,那必然存在很多重复的比较。现在的做法是,我把下面的字符串往前移动,使3和2对其,直接比较C和A是否一样。

    这里写图片描述

    这里写图片描述

    代码解析

    void cal_next(char *str, int *next, int len)
    {
        next[0] = -1;//next[0]初始化为-1,-1表示不存在相同的最大前缀和最大后缀
        int k = -1;//k初始化为-1
        for (int q = 1; q <= len-1; q++)
        {
            while (k > -1 && str[k + 1] != str[q])//如果下一个不同,那么k就变成next[k],注意next[k]是小于k的,无论k取任何值。
            {
                k = next[k];//往前回溯
            }
            if (str[k + 1] == str[q])//如果相同,k++
            {
                k = k + 1;
            }
            next[q] = k;//这个是把算的k的值(就是相同的最大前缀和最大后缀长)赋给next[q]
        }
    }

    KMP

    这个和next很像,具体就看代码,其实上面已经大概说完了整个匹配过程。

    int KMP(char *str, int slen, char *ptr, int plen)
    {
        int *next = new int[plen];
        cal_next(ptr, next, plen);//计算next数组
        int k = -1;
        for (int i = 0; i < slen; i++)
        {
            while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配,且k>-1(表示ptr和str有部分匹配)
                k = next[k];//往前回溯
            if (ptr[k + 1] == str[i])
                k = k + 1;
            if (k == plen-1)//说明k移动到ptr的最末端
            {
                //cout << "在位置" << i-plen+1<< endl;
                //k = -1;//重新初始化,寻找下一个
                //i = i - plen + 1;//i定位到该位置,外层for循环i++可以继续找下一个(这里默认存在两个匹配字符串可以部分重叠),感谢评论中同学指出错误。
                return i-plen+1;//返回相应的位置
            }
        }
        return -1;  
    }

    测试

        char *str = "bacbababadababacambabacaddababacasdsd";
        char *ptr = "ababaca";
        int a = KMP(str, 36, ptr, 7);
        return 0;

    注意如果str里有多个匹配ptr的字符串,要想求出所有的满足要求的下标位置,在KMP算法需要稍微修改一下。见上面注释掉的代码。

    复杂度分析

    next函数计算复杂度是(m),开始以为是O(m^2),后来仔细想了想,cal__next里的while循环,以及外层for循环,利用均摊思想,其实是O(m),这个以后想好了再写上。

    ………………………………………..分割线……………………………………..
    其实本文已经结束,后面的只是针对评论里的疑问,我尝试着进行解答的。

    进一步说明(2018-3-14)

    看了评论,大家对cal_next(..)函数和KMP()函数里的

    while (k > -1 && str[k + 1] != str[q])
            {
                k = next[k];
            }

    while (k >-1&& ptr[k + 1] != str[i])
                k = next[k];

    这个while循环和k=next[k]很疑惑!
    确实啊,我开始看这几行代码,相当懵逼,这写的啥啊,为啥这样写;后来上机跑了一下,慢慢了解到为何这样写了。这几行代码,可谓是对KMP算法本质得了解非常清楚才能想到的。很牛逼!
    直接看cal_next(..)函数:
    首先我们看第一个while循环,它到底干了什么。

    在此之前,我们先回到原程序。原程序里有一个大的for()循环,那这个for()循环是干嘛的?

    这个for循环就是计算next[0],next[1],…next[q]…的值。

    里面最后一句next[q]=k就是说明每次循环结束,我们已经计算了ptr的前(q+1)个字母组成的子串的“相同的最长前缀和最长后缀的长度”。(这句话前面已经解释了!) 这个“长度”就是k。

    好,到此为止,假设循环进行到 第 q 次,即已经计算了next[q],我们是怎么计算next[q+1]呢?

    比如我们已经知道ababab,q=4时,next[4]=2(k=2,表示该字符串的前5个字母组成的子串ababa存在相同的最长前缀和最长后缀的长度是3,所以k=2,next[4]=2。这个结果可以理解成我们自己观察算的,也可以理解成程序自己算的,这不是重点,重点是程序根据目前的结果怎么算next[5]的).,那么对于字符串ababab,我们计算next[5]的时候,此时q=5, k=2(上一步循环结束后的结果)。那么我们需要比较的是str[k+1]和str[q]是否相等,其实就是str[1]和str[5]是否相等!,为啥从k+1比较呢,因为上一次循环中,我们已经保证了str[k]和str[q](注意这个q是上次循环的q)是相等的(这句话自己想想,很容易理解),所以到本次循环,我们直接比较str[k+1]和str[q]是否相等(这个q是本次循环的q)。
    如果相等,那么跳出while(),进入if(),k=k+1,接着next[q]=k。即对于ababab,我们会得出next[5]=3。 这是程序自己算的,和我们观察的是一样的。
    如果不等,我们可以用”ababac“描述这种情况。 不等,进入while()里面,进行k=next[k],这句话是说,在str[k + 1] != str[q]的情况下,我们往前找一个k,使str[k + 1]==str[q],是往前一个一个找呢,还是有更快的找法呢? (一个一个找必然可以,即你把 k = next[k] 换成k- -也是完全能运行的(更正:这句话不对啊,把k=next[k]换成k–是不行的,评论25楼举了个反例)。但是程序给出了一种更快的找法,那就是 k = next[k]。 程序的意思是说,一旦str[k + 1] != str[q],即在后缀里面找不到时,我是可以直接跳过中间一段,跑到前缀里面找,next[k]就是相同的最长前缀和最长后缀的长度。所以,k=next[k]就变成,k=next[2],即k=0。此时再比较str[0+1]和str[5]是否相等,不等,则k=next[0]=-1。跳出循环。
    (这个解释能懂不?)

    以上就是这个cal_next()函数里的

    while (k > -1 && str[k + 1] != str[q])
            {
                k = next[k];
            }

    最难理解的地方的一个我的理解,有不对的欢迎指出。

    复杂度分析:

    分析KMP复杂度,那就直接看KMP函数。

    int KMP(char *str, int slen, char *ptr, int plen)
    {
        int *next = new int[plen];
        cal_next(ptr, next, plen);//计算next数组
        int k = -1;
        for (int i = 0; i < slen; i++)
        {
            while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配,且k>-1(表示ptr和str有部分匹配)
                k = next[k];//往前回溯
            if (ptr[k + 1] == str[i])
                k = k + 1;
            if (k == plen-1)//说明k移动到ptr的最末端
            {
                //cout << "在位置" << i-plen+1<< endl;
                //k = -1;//重新初始化,寻找下一个
                //i = i - plen + 1;//i定位到该位置,外层for循环i++可以继续找下一个(这里默认存在两个匹配字符串可以部分重叠),感谢评论中同学指出错误。
                return i-plen+1;//返回相应的位置
            }
        }
        return -1;  
    }

    这玩意真的不好解释,简单说一下:
    从代码解释复杂度是一件比较难的事情,我们从
    这里写图片描述

    这个图来解释。

    我们可以看到,匹配串每次往前移动,都是一大段一大段移动,假设匹配串里不存在重复的前缀和后缀,即next的值都是-1,那么每次移动其实就是一整个匹配串往前移动m个距离。然后重新一一比较,这样就比较m次,概括为,移动m距离,比较m次,移到末尾,就是比较n次,O(n)复杂度。 假设匹配串里存在重复的前缀和后缀,我们移动的距离相对小了点,但是比较的次数也小了,整体代价也是O(n)。
    所以复杂度是一个线性的复杂度。

    展开全文
  • 通俗易懂的KMP算法详解(严蔚敏版C语言)

    千次阅读 多人点赞 2019-03-16 09:33:44
    最近,需要复习KMP算法的next数组,然后回头看半年多后的我回头看半年多前自己综合别人内容写的介绍。 没错,自己也看不懂。然后,自己再根据自己的理解写了一下理解透彻的笔记,方便理解记忆,当然,以前的代码解释...
  • KMP算法详解

    千次阅读 多人点赞 2019-04-26 20:05:50
    KMP算法是一种字符串模式匹配算法,不同的来源讲解方式也不一样,很容易混乱,在这里以一种特殊的方式来讲解KMP算法,希望大家不再被这个问题所困扰。 一. 一些基础问题 什么是字符串的模式匹配? 给定两个串S=...
  • 数据结构之KMP算法(转)

    千次阅读 2018-07-02 20:48:58
    申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html什么是...KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字...
  • KMP算法

    千次阅读 2019-09-30 23:38:34
    KMP算法,又称模式匹配算法,能够在线性时间内判定字符串 T 是否为 S 的子串,并求出字符串 T 在 S 中各次出现的位置。 KMP算法比较晦涩难懂。本文对于思想介绍略简,侧重于实现。 问题模型与算法思路 问题模型: ...
  • kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
  • KMP算法和BM算法

    千次阅读 2018-06-06 22:38:28
    https://www.cnblogs.com/yjiyjige/p/3263858.html
  • 非常系统的KMP\MP算法讲解

    千次阅读 2015-07-14 13:20:02
    包含KMP和MP算法的区别,解决了大白书上的问题 点击打开链接
  • JAVA实现KMP算法

    2020-08-19 14:13:36
    JAVA实现KMP算法,使用java语言实现的kmp算法
  • 最近在学kmp算法,但是看了网上好多的讲解,都觉得好乱,有谁能给一个比较容易理解的版本么? 谢谢啦!
  • 考研408 | KMP算法

    2019-09-21 19:28:34
    如何求next数组: 1.求字符串的最长相等前后缀长度 2.得到的长度整体右移,右移后第一个空缺补-1,最后一个可以舍去 3.全部+1 快速求next数组的方法: 有的题目next数组下标是从-1开始的,也可以用这个方法(整体-1...
  • Sunday算法和KMP算法

    2015-01-16 20:46:20
    计划
  • KMP算法(C++)

    2018-07-18 15:55:44
    KMP算法: void getNext(const string&amp; needle,int next[]) { const int n = needle.size(); int i = 0; int j = -1; next[i] = j; while (i &lt; n) { if (j == -1 || needle[i] == needle[j...
  • 并不是什么独创的秘籍,也不是什么高招,就是根据公式来进行计算的方法,我将它程序化了而已.
  • KMP算法源代码 C语言

    2020-07-30 23:30:21
    KMP算法源代码 C语言 KMP算法源代码 C语言 KMP C语言
  • 复习算法与数据结构这课的KMP算法,到现在对前缀函数很困惑。各位大牛们就举个例子来说说吧。 字符串"abcaababc" 求其KMP前缀函数。 我求出来next[i]:{-1,0,0,-1,1,0,2,0,0},这是不是KMP前缀函数啊?
1 2 3 4 5 ... 20
收藏数 57,124
精华内容 22,849
关键字:

kmp算法