精华内容
下载资源
问答
  • kmp算法中next和nextval计算方法和代码总结
    千次阅读
    2021-01-19 23:35:01

    此篇文章总结的 基于kmp中的模式串方式

    关于next图解如下

    举例:字符串 “ababaa”

    索引012345
    字符ababaa
    next001123

     

     

     

     

    next定义写法

    从索引1位置开始计算,除去第i位置,从0到 i-1,前后缀中最长重复字符长度

    备注如果没有前后缀元素只要自己默认为0,如果没有相同元素默认为1

    next[0]=0 默认0

    next[1] =0 从1位置开始计算 默认为0

    next[2] = 1,此时ab, 前后缀中没有公有为1

    next[3] = 1,此时aba, 字符串前缀组合a,ab 字符串后缀组合 b,ba;前后公有最长a,所以为1

    next[4] = 2,此时abab, 字符串前缀组合a,ab,aba, 字符串后缀组合 b,ab,bab;前后公有最长ab,所以为2

    next[5] = 3,此时ababa, 字符串前缀组合a,ab,aba, 字符串后缀组合 b,ab,aba;前后公有最长aba,所以为3

    求解代码如下:

    /*
    *@author: 赵秋然
    *@date:2021年1月19日
    *@description:kmp中next求解
    */
    void kmp_next(char patt[], int next[])
    {
        int i = 0, j = 1, n = strlen(patt);
    
        next[i] = next[j] = 0;
        while (j < n)
        {
            if (i == 0 || patt[i] == patt[j])
            {
                ++i;
                next[j + 1] = i;
                ++j;
            }
            else
            {
                i = next[i];
            }
    
        }
    }

    nextval求解方法

    nextval是在next方式上的升级改进,使得模式串回退跟快速有效,减少next中不必要的比较

    索引012345
    字符ababaa
    next001123
    nextval001013

     

     

     

     

     

    计算方式 

    默认前2位为0

    nextval计算方式需要根据next结果

    索引2时,元素a,next值为1,索引为1,元素b, a≠b ;nextval[2] = next[2]=1

    索引3时,元素b,next值为1,索引为1,元素b, b=b ;nextval[3] = next[1] = 0

    索引4时,元素a,next值为2,索引为2,元素a, a=a ;nextval[4] = next[2] = 1

    索引5时,元素a,next值为3,索引为3,元素b, a≠b ;nextval[5] = next[5] = 3

    根据以上结论得出:

    当前索引与next索引值相同,此时索引值为next索引值

    如果不同,此时索引值为next值

    /*
    *@author: 赵秋然
    *@date:2021年1月21日
    *@description:kmp中nextval求解
    */
    
    void kmp_nextval(char patt[], int next[])
    {
        int i = 0, j = 1, n = strlen(patt);
        next[i] = next[j] = 0;
    
        while(j < n)
        {
            if(i == 0 || patt[i] == patt[j])
            {
                  if(patt[j+1] == patt[i+1])
                  {
                     next[j+1] = next[i+1];
                  }
                  else
                    {
                        next[j+1] = i+1;
                  }
    
                  ++i;
                  ++j;
            }
            else
            {
                i = next[i];
            }
        }
    }

    为什么会引入nextval呢?

    举例:

    索引012345
    字符aaaaab
    next001234
    nextval000004

     

     

     

     

     

    模式串aaaaab,构建next数组后,对字符进行匹配时,如果发现字符不匹配那么next就需要回退

    如果此时是索引4位置不匹配,那么根据next值就需要回退到3,2,1的不断回退,匹配速度变慢,效率下降

    nextval方式直接回退到首位置,减少了不必要的回退

     

    更多相关内容
  • 网上看了很多的解析,好多博主抛出一个概念,然后没有解析,对我这种弱渣来说更加懵逼了~下面是我总结的一个简单的计算方法 首先介绍2个概念,字符的前缀和后缀(这里的前缀是不包括最后一个字符的子串,后缀是不...

    原题:
    在这里插入图片描述
    大一学的数据结构全忘了,做题看到的,整个人都懵了。。
    网上看了很多的解析,好多博主抛出一个概念,然后没有解析,对我这种弱渣来说更加懵逼了~下面是我总结的一个简单的计算方法

    首先介绍2个概念,字符串的前缀和后缀(这里的前缀是不包括最后一个字符的子串,后缀是不包含第一个字符的子串)。
    拿题目中的字符串a=’‘babab’'举例,
    首先第一位0,第二位1。这个是固定的。

    第三位,字符串是“bab”,这时候“bab”的前缀有b,ba;后缀有ab,b,可以看出前后缀相等的最长的字符串只有b,因为b的长度是1,所以这里第三位的next值就是1。

    第四位,字符串是“baba”,前缀是b,ba,bab;后缀是aba,ba,a。这里可以看出前后缀相等的最长的字符串是ba,长度是2,因此第四位的next值是2。

    第五位,字符串是“babab”,前缀是b,ba,bab,baba;后缀是abab,bab,ab,b。这里可以看出前后缀相等的最长的字符串是bab,长度是3,因此第五位的next值是3。

    展开全文
  • 数据结构kmp算法 next数组计算 如何使用next匹配


    本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了)
    为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼

    KMP介绍

    提示:以下信息来源百度

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

    上面讲了kmp需要求匹配字符串的next数组来快速匹配,那我们先来讲解一下如何求next数组


    一、求Next数组

    求Next数组前我们需要了解字符串的前缀表后缀表

    前后缀表

    如字符串“ABCD”的前后缀表

    在这里插入图片描述

    了解完字符串前后缀,接下来我们要开始求最长公共前后缀

    求最长公共前后缀

    我们以“aabaac”为例

    在这里插入图片描述

    字符串中要没有公共前后缀就为0

    从以上方法就能求出字符串“aabaac”的最长公共前后缀数组
    [0,1,0,1,2,0]

    最长相等前后缀表转Next数组

    当然变成Next数组前还需要进行简单的处理(其实也就把最长公共前后缀数组右移而已)
    在这里插入图片描述

    在最长公共前后缀前面加上 -1 并去掉最后一位就是next数组了
    Next数组的第一位永远是-1,第二位永远是0

    注意:Next数组有很多种求法,依据匹配字符串的代码来做选择,我选择的方法next数组第一位是-1,还有另一种方法开头是0,但原理都是相同的所以不必纠结


    二、使用Next数组来匹配字符串

    为了能较好体现kmp算法:
    主串:“aaacaacaaad
    模式串:“aaad
    模式串Next数组:[-1,0,1,2]

    在主串和匹配串字符相同的情况下,指针 i 和 j 后移

    或者遇到主串和匹配串字符不相同但next值为-1时指针 i 和 j 后移

    步骤一
    1i、1j、2i、2j代表指针位置及步骤,中间字符相等的地方我就不讲了,就主要讲重点的地方

    指针4i4j的字符不相同,不匹配位置的next值为2(蓝色的a),所以需要将匹配串右移到匹配串索引2的位置
    请添加图片描述
    步骤二
    匹配串后移后指针ij的字符依然还是不相同,不匹配位置的next值为1(蓝色的a),所以需要将匹配串右移到匹配串索引1的位置
    请添加图片描述
    步骤三
    匹配串后移后指针ij的字符依然还是不相同,不匹配位置的next值为0(蓝色的a),所以需要将匹配串右移到匹配串索引0的位置
    请添加图片描述
    步骤四
    匹配串后移后指针ij的字符依然还是不相同,但这时next值为-1,这就需要指针i和j向后移
    请添加图片描述
    步骤五
    指针i和j后移后,(中间字符相同的地方就不解说了),指针到3i和3j的字符不相同,next值为1,然后就和之前讲的步骤一样,需要将匹配串右移到匹配串索引1的位置
    请添加图片描述
    步骤六
    后面的步骤就不再多叙述,自己看图分析
    请添加图片描述
    步骤七
    请添加图片描述

    步骤八
    然后这就匹配完成了
    请添加图片描述


    总结

    代码后续会补充
    非常感谢您能看到这,本人第一次写文章,所以我可能讲的不是很好,如有问题望大家能多多提醒,感谢。下次讲sunday算法
    注:如看不懂,可以的话,麻烦您在评论区中发句看不懂,好让我知道我写的烂不烂

    展开全文
  • 字符串next和nextval值的计算

    千次阅读 2020-03-20 23:52:45
    字符串next和nextval值的计算 针对字符串ababaabab,计算next和nextval的值。 第一行是序号,从0开始。 第二行是字符串的元素 第三行是next值,为当前位置前面字符串收尾重复的最长字符个数。 第四行是...

    字符串next和nextval值的计算

    针对字符串ababaabab,计算nextnextval的值。

    • 第一行是序号,从0开始。

    • 第二行是字符串的元素

    • 第三行是next值,为当前位置前面字符串收尾重复的最长字符个数。

    • 第四行是nextval值,当以next和以i为索引的字符不相同时,nextval值就是next值。当两个字符相同时,nextval值是以next为索引的nextval值。

    next 值的计算

    举个例子,当i=5时,计算方法如下:

    image-20200320233907924

    其中,0和1的next值固定为-1和0.

    nextval值的计算

    0的nextval值固定为-1

    i012345678
    sababaabab
    next-100123123
    nextval-10-10-130-10

    有时候下标从1开始,则nextval就是010104101.

    展开全文
  • 题目描述 字符的子串定位称为模式...请参考教材next数组的计算公式与算法,编程实现之。 输入 一个模式,仅由英文小写字母组成。长度不大于100。 输出 输出模式对应的移动数组next。每个整数后跟一个空格。 样
  • 大多数据结构课本中,涉及的内容即的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • 3.第三位的next值:看第二位的模式为b,对应的next值为1,则将第二位的模式b与j=1的模式进行比较,不同,则没有相同的字符,值为1。 4.第四位的next值:看第三位的模式为c,对应的next值为1,则将第三位的...
  • KMP算法next数组计算--字符方式

    千次阅读 2017-06-19 23:51:17
    用字符的方式说明模式匹配中KMP算法求解next数组的方式
  • 求解nextnext数组的求解方法:首先第一位的next值直接给0,第二位的next值直接给1,后面求解每一位的next值时,都要前一位进行比较。首先将前一位与其next值的对应位进行比较,若相等,则该位的next值就是前一位的...
  • 在KMP算法中,最关键的就是求解next数组了。那么如何快速求解next数组呢? 已知模式:A B C D A B D D A 其next数组:0 0 0 0 120 0 1 那么是如何求证出来的呢? 首先字符从左至右遍历。 第一个字符A的next...
  • 模式next()函数值

    万次阅读 多人点赞 2020-05-27 17:44:37
    模式:ababaaaba next:011234223 方法: 前两位是0和1 第三位:前一位b对应的next值为1,1对应的a(在数组中第一个数为a)和b不相同,故第三位的next值为1 第四位:前一位a对应的next值为1,1对应的a和a相同,故...
  • 主要介绍了C++ 数据结构之kmp算法中的求Next()函数的算法的相关资料,需要的朋友可以参考下
  • kmp算法计算模式next

    千次阅读 2016-11-18 19:22:27
    此时意味着主和子串的下标都需要加1; //2、val={0,1...k-1}中的任意值,k为正在比较的第k个字符,也就是说当他们不相等时,需要回溯到val继续比较; void get_next(char *p,int n) { int i=0,k; k=next[0]=-1;/...
  • next数组的作⽤:当模式的第j个字符失配时,从模式的第next[j]的继续往后匹配。 ①、任何模式都一样,第一个字符不匹配时,只能匹配下一个子串,<font color='red'>next[1]都无脑写0 ②、任何模式都一样,第...
  • 计软刷题时刷到一个题目,模式p为“abaac”,求其next函数。代码就不解析了(我也没咋看),为了应试总结了一个快速答题技巧。 首先,按位序、模式next函数写下来: 位序 1 2 3 4 5 模式...
  • 字符串next函数求值

    千次阅读 多人点赞 2017-10-11 21:31:26
    先看看next数据值的求解方法  位序 1 2 3 4 5 6 7 8 9 模式 a b a a b c a b c  next值 0 1 1 2 2 3 1 2 3 next数组的求解方法是: 1.第一位的next值为0 2.第二位
  • 其实计算next的值本身也就是对模式进行模式匹配,我们一起看看计算next的值的过程; 当模式 P=“ababcabaababb” 时计算它的next值。 比如: 代码: void get_next(m_1 A) { int i=-1,j=0; A-&...
  • 求字符next值的两种方法

    万次阅读 多人点赞 2019-03-01 22:06:04
    自己目前掌握的有两种求字符串next值的方法,下面用简单通俗的描述记录下来。 以字符串ababaaababaa(下文也称为字符串s)为例,其next值为011234223456,下面介绍两种求解方法,其中无论是字符串s或是next数组,下标...
  • KMP算法初始化模式next数组

    千次阅读 2020-05-14 17:03:52
    在使用KMP算法处理字符查找问题的过程当中,可以利用模式本身的对称性,在移动模式的时候,尽量多的往后移动,减少无用的查找过程,而模式本身的对称性一般是保存在一个next数组里面的,下面来讨论下怎么...
  • 例如:现在有一个文本S=“BBC ABCDAB ABCDABCDABDE”和一个搜索(模式)p="ABCDABD",要查找p在s中的位置。(暴力算法的代码就不贴了,此算法的时间复杂度最好为O(n+m)、最坏为O(nm)) 这样只能一个一个的去...
  • KMP算法相比于朴素的模式匹配算法,其改进之处在于:利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的距离。...我们介绍两种方法来计算模式next函数 方法一:传统方法 方法二:简便方法...
  • KMP 算法以及 next 数组计算

    千次阅读 2018-08-23 17:01:26
    看本文的同志们需要注意的是,本文没有按照一般的套路来介绍KMP算法,而是侧重于介绍KMP算法为什么这样做,关于KMP算法和next非常值得一看的博客推荐如下: https://www.cnblogs.com/tangzhengyue/p/4315393.html ...
  • 的模式匹配KMP算法中next[]数组的求解总结 步骤(1) 初始化 next[1]=0 next[2]=1; 步骤(2) 求next[j],令k=next[j-1] 步骤(3) S[j-1] S[k] 比较大小 = , next[j]=...
  • KMP快速计算next与nextval

    千次阅读 多人点赞 2019-06-10 09:54:41
    最近在研究数据结构,碰到了计算next与nextval值,查看了大量资料,发现这个方法最是清楚明白,整理后贡献出来,有问题可以留言哟! 方法1:引入了一个maxL,在计算nextval时,比较方便。强烈建议读者按照思路算一遍,...
  • 首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值...
  • 计算next和nextVal值

    千次阅读 2020-04-09 16:58:19
    计算时只用到子串,也就是模式(这里用到一个maxL值) 这里模式为:abaabcac 第一步将模式写上序号,我们这里从1开始(有的从0开始,建议充1开始) 然后计算出maxL值,列出从第一个开始的子串,找出相等的...
  • 理解next数组的计算方式

    千次阅读 2019-01-21 20:52:30
    i 0 1 2 3 4 5 6 7 8 9 10 11 s a b a b a a a b a b a a next[i] -1 0 0 1 2 3 1 1 2 3 4 5 先计算前缀next[i]的值:...
  • Next 值与 Nextval 值的计算

    万次阅读 多人点赞 2018-05-20 20:42:05
    KMP算法对模式求解其Next值和Nextval值的计算方法 Next值的计算 方法一 方法二 Nextval值的计算 模式S = “abaabcac” ,求其 Next 数值序列: 1 2 3 4 5 6 7 8 a b a a b...
  • KMP算法中计算next数组的代码

    千次阅读 2020-11-04 17:24:55
    如:严蔚敏《数据结构》将模式下标从1开始计数,故定义next[1]=0,next[2]=1。李春葆《数据结构》将模式下标从0开始计数,故定义next[0]=-1,next[1]=0。但这两种定义方式,不影响它们有一致的计算方法,即“若...
  • 哈哈哈KMP算法之Next算法之如何计算简的描述抛出疑问所以看懂下面的图最简单的实现 KMP算法之Next算法之如何计算 简的描述 K,J为两个“指针”,K指向前缀,J指向后缀。 当P[K]==P[J],则 K++,J++,匹配下一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 214,316
精华内容 85,726
关键字:

串的next计算