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-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算法—终于全部弄懂了

    万次阅读 多人点赞 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-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算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • KMP算法详解

    万次阅读 多人点赞 2015-12-12 11:13:44
    kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简单明了地将其讲清楚。在此,综合网上比较好的...
  • KMP

    2019-09-17 10:08:13
    KMP
  • 从头到尾彻底理解KMP

    2020-07-30 23:31:58
    CSDN博主写的一遍KMP算法,图文并茂,经过作者多次改版,日臻完善,非常详细介绍了KMP的方方面面。非常实用,值得一读。
  • 通俗易懂的KMP算法详解(严蔚敏版C语言)

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

    千次阅读 2019-07-21 22:47:36
    kmp详解及代码 参考资料《大话数据结构》
  • kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
  • KMP算法是模式匹配专用算法。它是在已知模式串的next或nextval数组的基础上执行的。如果不知道它们二者之一,就没法使用KMP算法,因此我们需要计算它们。KMP算法由两部分组成:第一部分,计算模式串的next或nextval...
  • 转自知乎-我见过最通俗易懂的KMP算法详解

    万次阅读 多人点赞 2018-04-15 18:23:22
    KMP算法真的不适合这样去学。最好的办法是先搞清楚它所用的数据结构是什么,再搞清楚怎么用,最后为什么的问题就会有恍然大悟的感觉。我试着从这个思路再介绍一下。大家只需要记住一点,PMT是什么东西。然后自己...
  • 【模式匹配】之 —— KMP算法详解及证明

    千次阅读 多人点赞 2013-05-15 22:18:14
    一 RevisionsHistory 1 ...KMP算法是用来干什么的KMP算法是怎样产生的从暴力搜索算法讲起KMP算法的思想KMP算法的代码实现KMP算法改进使用KMP算法在目标字符串中查找所有匹配的位置使用Z-BOX算法计算next数组 五
  • KMP算法详解及Java实现

    2019-09-09 11:44:13
    KMP算法详解及Java实现KMP算法描述部分匹配算法原理部分匹配算法实现(Java)KMP匹配算法Java实现 以前在学习计算机数据结构时,涉及到基础算法KMP算法,学习了好几次,在网上找了很多资料,说得也不是清楚,后来在...
  • 大名鼎鼎的KMP算法 来吧今天我们一起搞懂它!???? 首先不太清楚KMP算法的可以戳这里!百度百科欢迎您~ KMP算法简介: KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主...
  • kmp算法简单介绍

    2019-07-30 17:18:22
    kmp算法解决的是从主串中搜索子串的算法,时间复杂度为O(n+m);其中建立next数组用时O(m),搜索主串用时O(n); 主要用于替代用双重循环来寻找子串(时间复杂度为O(m*n)); Kmp算法的优点在于它的时间是...
  • KMP算法及其应用

    千次阅读 2017-08-01 21:23:24
    前言今天学习了一个新算法:KMP算法 其实很久以前学过早忘了 KMP算法是用于处理字串问题的算法。参考Matrix67的博客:KMP算法详解|Matrix67KMP算法的原理假设有字符串A和B,要求判断B是否是A的字串 其实就是对于...
  • KMP算法Next数组计算

    万次阅读 多人点赞 2018-06-28 22:45:38
    KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列(其实是)。先看看题吧。 (2011年下半年上午题) (2012年上半年上午题) 其实做这个题很简单,我先说说这个题里的各种概念。...
  • BF算法、KMP算法、改进的KMP算法

    千次阅读 2018-08-14 17:48:43
    BF算法、KMP算法、改进的KMP算法,以上几种算法都是模式匹配算法,即找模式串在主串中第一次出现的位置。 BF算法: 如上图所示 主串:”abcaba” 子串:”aba” 思路:从主串第一个开始和子串第一个匹配,如果...
  • kmp算法的c++实现

    千次阅读 2018-10-31 12:46:56
     KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串...
1 2 3 4 5 ... 20
收藏数 36,503
精华内容 14,601
关键字:

kmp