精华内容
下载资源
问答
  • 首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值...

    刚刚开始遇到这个问题说实话完全懵逼,然后简单搜了下,还是理解的模棱两可。最后看了几篇博客,现在才算是真正的理解了。

    首先在将例子之前先说说这个next数组求解的思路:

    第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,如果不等,向前继续寻找next值对应的内容与前一位进行比较(向前继续寻找next值对应的内容与next值对应的内容的next前一位进行比较),直到找到某个位上的内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。

    求串′ababaaababaa′的next数组

    模式串ababaaababaa
    下标123456789101112

    1、前两位:next数组前两位规定是0,1 即前两位ab对应的next数组为01,则:

    模式串ababaaababaa
    下标123456789101112
    next数组01          

    2、接下来看第三位,按照next数组求解方法。第三位a的前一位为第二位的b,b的next值为1对应内容为a,b与a不同,向前继续寻找next值对应的内容来与前一位进行比较。因为找到第一位都没有找到与前一位相等的内容,所以第三位a的next值为1,则:

    模式串ababaaababaa
    下标123456789101112
    next数组011         

    3、接下来看第四位b,b的前一位a的next值1对应内容为a,相同,所以该位b的next值就是前一位a的next值加上1,即为2

    模式串ababaaababaa
    下标123456789101112
    next数组0112        

    4、接下来看第五位a,a的前一位b的next值2对应内容为b,相等,所以该位a的next值就是前一位b的next值加上1,即为3

    模式串ababaaababaa
    下标123456789101112
    next数组01123       

    5、接下来看第六位a,a的前一位a的next值3对应内容为a,相等,所以该位a的next值就是前一位a的next值加上1,即为4

    模式串ababaaababaa
    下标123456789101112
    next数组011234      

    6、接下来看第七位a,a的前一位a的next值4对应内容为b,不相等,向前继续寻找next值对应的内容来与前一位进行比较,b的next值2对应的内容为b,依旧不相等,继续向前寻找,第二位b的next值1对应内容为a,相等。因为是在第二位b处实现的相等,所以第七位a的next值为第二位b的next值上加1,即为2

    模式串ababaaababaa
    下标123456789101112
    next数组0112342     

    7、接下来看第八位,同样道理,得出b的next值为2

    模式串ababaaababaa
    下标123456789101112
    next数组01123422    

    8、接下来看第九位,前一位b的next值2对应内容为b,相等,所以此处next值为3

    模式串ababaaababaa
    下标123456789101112
    next数组011234223   

    9、第十位同理可得,为4

    模式串ababaaababaa
    下标123456789101112
    next数组0112342234  

    10、第十一位a的前一位b的next值4对应内容为b,相等,所以此处next值为5

    模式串ababaaababaa
    下标123456789101112
    next数组01123422345 

    11、最后,第十二位同理可以得到next值位6

    模式串ababaaababaa
    下标123456789101112
    next数组011234223456

    展开全文
  • 这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正! 《数据结构C语言版第2版》的课后习题里有这两道题(答案是CA) 书上求next数组和nextval数组的代码如下: ...计算ababaaababaanext数组: ne

    这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正!

    《数据结构C语言版第2版》的课后习题里有这两道题(答案是CA)
    在这里插入图片描述
    书上求next数组和nextval数组的代码如下:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    快速求next数组的方法:

    1. i == 1时,next[1]的值为0
    2. i >=2 时,next[i]的值为字符串 [1,…,i-1]的最大公共前后缀的长度再加1
      前缀不包括最后那个字符,后缀不包括第一个字符,比如aaaaa的公共前后缀是aaaa,而不是aaaaa

    计算ababaaababaa的next数组:
    next[1] = 0
    next[2]:子串[1,1]的子串是a,最大公共前后缀为0,所以next[2] = 0+1 = 1
    next[3]:子串[1,2]的子串是ab,最大公共前后缀为0,所以next[3] = 0+1 = 1
    next[4]:子串[1,3]的子串是aba,最大公共前后缀为1,所以next[4] = 1+1 = 2
    next[5]:子串[1,4]的子串是abab,最大公共前后缀为2,所以next[5] = 2+1 = 3
    next[6]:子串[1,5]的子串是ababa,最大公共前后缀为3,所以next[6] = 3+1 = 4
    next[7]:子串[1,6]的子串是ababaa,最大公共前后缀为1,所以next[7] = 1+1 = 2
    next[8]:子串[1,7]的子串是ababaaa,最大公共前后缀为1,所以next[8] = 1+1 = 2
    next[9]:子串[1,8]的子串是ababaaab,最大公共前后缀为2,所以next[9] = 2+1 = 3
    next[10]:子串[1,9]的子串是ababaaaba,最大公共前后缀为3,所以next[10] = 3+1 = 4
    next[11]:子串[1,10]的子串是ababaaabab,最大公共前后缀为4,所以next[11] = 4+1 = 5
    next[12]:子串[1,11]的子串是ababaaababa,最大公共前后缀为5,所以next[12] = 5+1 = 6
    (不需要求next[13])
    所以这个next数组就求完了,答案为[0,1,1,2,3,4,2,2,3,4,5,6]

    快速求nextval数组的方法:

    1. 先求出next数组
    2. 先拷贝next数组的所有值到nextval
    3. 假设字符串是s,长度为n,从1到n逐一扫描nextval数组
    4. 如果s[nextval[i]] == s[i],那么把nextval[i]的值改成nextval[nextval[i]]的值,否则就保持不变。

    就写到这了,睡觉!

    展开全文
  • 在使用KMP算法处理字符查找问题的过程当中,可以利用模式本身的对称性,在移动模式的时候,尽量多的往后移动,减少无用的查找过程,而模式本身的对称性一般是保存在一个next数组里面的,下面来讨论下怎么...

    在使用KMP算法处理字符串查找问题的过程当中,可以利用模式串本身的对称性,在移动模式串的时候,尽量多的往后移动,减少无用的查找过程,而模式串本身的对称性一般是保存在一个next数组里面的,下面来讨论下怎么初始化next数组的值。

    先来看一下下面这个例子:
    示例
    申明一下:下面说的对称不是中心对称,而是中心字符块对称,比如不是abccba,而是abcabc这种对称。

    分析:
    i=0:模式串为m,最长前缀子串和后缀子串都为空,next[0] = 0;
    i=1:模式串为mb,最长前缀子串为m,最长后缀子串为b,无对称块,next[1] = 0;
    i=2,i=3:同理,next[2] = 0,next[3] = 0;
    i=4:模式串为mbwtm,最长前缀子串为mbwt,最长后缀子串为bwtm,对称块为m,长度为1,next[4] = 1;
    i=5:模式串为mbwtmb,最长前缀子串为mbwtm,最长后缀子串为bwtmb,对称块为mb,长度为2,next[5] = 2;
    i=6:模式串为mbwtmbw,最长前缀子串为mbwtmb,最长后缀子串为bwtmbw,对称块为mbw,长度为3,next[6] = 3;

    i=13:模式串为mbwtmbwmbwtmbw,最长前缀子串为mbwtmbwmbwtmb,最长后缀子串为bwtmbwmbwtmbw,对称块为mbwtmbw,长度为7,next[13] = 7;
    i=14:模式串为mbwtmbwmbwtmbwt,最长前缀子串为mbwtmbwmbwtmbw,最长后缀子串为bwtmbwmbwtmbwt,对称块为mbwt,长度为4,next[14] = 4;
    i=15:模式串为mbwtmbwmbwtmbwtb,最长前缀子串为mbwtmbwmbwtmbwt,最长后缀子串为bwtmbwmbwtmbwtb,无对称块,next[15] = 0;

    根据上面的例子,可以总结一下下面的规律,后面出现模串的位置用P替代:

    1. 当前字符的前一个字符的对称块长度为0(next数组对应位置的值为0)时,只需要比较当前字符跟模式串的第1个字符P[0],若相等则当前位置对应的next数组值为1,否则为0;
    2. 按照规律1,如果当前字符的前1个字符的对称块长度为1,此时只需要比较当前字符跟模式串的第2个字符P[1],若相等则当前位置对应的next数组值为2。如果当前字符的前1个字符的对称块长度为2,此时只需要比较当前字符跟模式串的第3个字符P[2],若相等则当前位置对应的next数组值为3。例如当前位置i=6时,可以知道i=5时,next[5] = 2,此时只需要比较模式串位置i=6的字符w跟模式串位置i=next[5]=2位置的字符P[2]=w是否相等(前面的两个字符mb在i=5时已经比较过且相等了),相等话next[6] = next[5] + 1 = 3;
    3. 按照规律2,如果一直想等的话,那就可以一直累加,但是总会出现不相等的时候,如果出现了不相等的情况,并不是说完全没有对称块了,只是对称块的长度变短了,需要重新计算。

    针对上面规律3出现的不相等的时候,怎么计算此时next数组对应位置的值,我们以上面例子的i=14为例子来说明:

    1. next[13] = 7,表示模式串的i=0到i=6这一串跟i=7到i=13这一串是完全相等的,设置K=7,K表示前一位置的最长对称块的长度。
    2. i=14时,由于P[14] = t != m = P[7]不相等,所以可以肯定的是i=14位置的next[14]的值肯定比next[13]小,且只能在i=0到i<7这一区间内寻找了.
    3. 因为P[14] != P[7],所以P[0-6]这一段肯定不是对称块了。那么新的对称块是从i=0到i等于多少的位置呢?可以知道P[0-6] == P[7-13],所以可以先计算P[0-6]的对称块长度,即next[K-1]的值。结果是mbw,即P[0-2] == P[4-6],从P[0-6] == P[7-13]可以得到P[4-6] = P[11-13],所以[0-2] == P[11-13],然后比较P[14]是否等于P[3]。
    4. 如果相等,则next[14] = next[K-1] + 1 = next[7-1] + 1 = 4。(如果不相等,则重复步骤3和4。假设P[14] = x != t = P[3],则k = next[k-1] = 3,重复第3步,从P[0-2]里面寻找最长的对称块,此时next的值都为0,所以此时next[14] = 0)。

    下面列一下代码并配合注释,帮助理解。

    void initNext(const char P[],int next[]) { 
    	int i;						//i:模式串下标
        int k;						//k:最大对称块长度 
        int pLen = strlen(P);		//pLen:模式串的长度 
        next[0] = 0;					//模式串的第一个字符的对称块长度为0 
    
    	//for循环,从第二个字符开始,依次计算模式串每一个字符对应的next数组值 
        for (i = 1,k = 0; i < pLen ; i++){
        	//递归的求出P[0]···P[i]的最大的相同的前后缀长度k 
    		while(k > 0 && P[i] != P[k]) {
    			//当P[i] != P[k]时,参考上面例子中的第三步,需要循环计算k的值
    			k = next[k-1];   
    		}       
    		//如果相等,那么最大相同前后缀长度加1(参考上面说的规律2)
           	if (P[i] == P[k]){
     			k++;
    		}
    		//赋值k到next数组的i位置
    		next[i] = k;
    	}
    }
    

    注意一下,next 数组考虑的是除当前字符外的最长相同对称快,所以通过上述方法求得的各个位置的最大相同对称块数组next之后,只要稍作变形即可:将next数组中的元素整理往后移动一位,且next[0] = -1

    展开全文
  • 求字符‘abaabcac’的next数组和nextval数组

    千次阅读 多人点赞 2020-03-06 17:53:52
    今天刷到一个笔试题,求一个字符在KMP算法下的next数组 几番百度和看题解,居然大多数的题解都有毛病被一顿吐槽 最后,通过一张动图搞懂了计算的原理 如下: 本图来自这个博客 正如下面评论说的,文章写得可能不...

    今天刷到一个笔试题,求一个字符串在KMP算法下的next数组和nextval数组

    几番百度和看题解,居然大多数的题解都有毛病被一顿吐槽

    几番周折终于搞懂了怎么求next数组和nextval数组,在此记录下

    题目是:

    求字符串abaabcac的next数组和nextval数组:

    结果如下:
    在这里插入图片描述
    注意: 这里的数组下标从1开始数

    首先,通过一个动图来了解下求next数组的过程

    在这里插入图片描述
    本图来自这个博客

    我觉得这张图已经很直观了,下面我就对求解的方法做一点自己的总结

    求next数组
    • next[1] = 0
    • next[2] = 1
    • 当i > 2 时,如:求next[5]
      • 求next[0]~next[i - 1]所构成的串的首子串和尾子串(首子串不包括最后一个,尾子串不包括第一个)
        next[0]~next[4]为:abaa
        首子串:a,ab,aba
        尾子串:baa,aa,a
      • 计算首尾子串中相同的子串的长度
        相同的子串为a,长度为1
      • next[i] = length + 1
        求得长度为1,1+1 = 2,所以next[5] = 2
    求nextval数组
    • 求nextval[i]的值,我们要比较String[i]和String[next[i]]的值
      • 如果String[i]和String[next[i]]的字符相等,那么nextval[i]的值就等于nextval[next[i]]的值,
      • 如果String[i]和String[next[i]]的字符不相等,那么nextval[i]的值就等于next[i]的值。

    就上面的串进行演示:

    • i = 1
      nextval[1] = 0
    • i = 2
      nextval[2] = 1
    • i = 3
      next[3] = 1
      String[3] = a
      String[1] =a == a
      nextval3] = nextval[1] = 0
    • i = 4
      next[4] = 2
      String[4] = a
      String[2] = b != a
      nextval[4] = next[4] = 2
    • 同理,可以求出所有的啦

    花了一个多小时百度和总结,有了比较深刻的印象了,下次遇到就能轻松应对了

    展开全文
  • KMP算法的next数组

    2015-11-28 20:17:27
    关于字符匹配里,KMP算法中next实现实现原理。关于字符匹配里,KMP算法中next实现实现原理。
  • next数组
  • next数组求解详解

    万次阅读 多人点赞 2017-08-20 20:52:59
    next数组求解详解,以'ababaaababaa'为例
  • next数组详解

    千次阅读 2020-05-20 00:20:37
    next数组详解思路前缀、后缀、部分匹配值部分匹配(Partial Match,PM)表next数组求解方法代码实现 前缀、后缀、部分匹配值 "前缀"指除了最后一个字符以外,字符的所有头部组合; "后缀"指除了第一个字符以外,...
  • 算法:next数组的求法详解

    万次阅读 多人点赞 2019-01-27 16:26:48
    在牛客网刷题遇到了求next数组的题型,结果在学校学的没有牢记,做错了,还是要多刷题做总结啊。 我们先口述说明一下next数组的求解方法: 我们能确定next数组第一二位一定分别为0,1,后面求解每一位的next值时,...
  • 假设求ababaaababaa′的next数组 模式串ababaaababaa 下标 1 2 3 4 5 6 7 8 9 10 11 12 1、前两位:next数组前两位一定是0,1 即前两位ab对应的next数组为01,则: 模式...
  • KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。 计算前缀 Next[i] 的值: 我们令 next[0] = -1 。从 next...
  • kmp算法java代码实现——使用next数组实现对目标字符查找 代码如下: import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ...
  • 的模式匹配KMP算法中next[]数组的求解总结 步骤(1) 初始化 next[1]=0 next[2]=1; 步骤(2) 求next[j],令k=next[j-1] 步骤(3) S[j-1] S[k] 比较大小 = , next[j]=...
  • next数组两种求法

    万次阅读 多人点赞 2018-08-22 15:03:37
    (1)看到网上同一个字符求 next 数组的值有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1 开头看...
  • 继上一篇关于模式匹配算法的博文,我想在...在这里我们用next数组来记录模式各个位置的j值变换。 让我们用一个例子来说明上述概念: 假设主S=abcdefgab 匹配为T=abcdex 如果我们按照BF模式匹配算法来处理...
  • 数据结构之next数组求法

    千次阅读 2020-12-18 23:17:37
    数据结构之next数组的求法 方法: 我们能确定next数组第一二位一定分别为0,1,后面求解每一位的next值时,根据前一位进行比较。从第三位开始,将前一位与其next值对应的内容进行比较,如果相等,则该位的next值...
  • 例:给出一个字符序列:ababaaababaa。利用KMP算法分别求出next数组和nextval数组 分析: 数组索引:0-n 逻辑索引:1-n next数组: 1、next[0]=0,next[1]=1; 2、当判断一个字母X的next值时,需要将前一个位置的...
  • KMP算法理解之next数组

    千次阅读 2018-09-20 15:03:10
    .next数组的求法(这个是真的有点困难的。。。还好自己又搞明白了) 下面以字符串ababaaababaa为例说明一下 next[i](i从1开始算)代表着,除去第i个数,在一个字符里面从第一个数到第(i-1)字符前缀与后缀...
  • 提到子串的模式匹配算法就不得不提到大名鼎鼎的KMP算法,而KMP算法的实现离不开next数组,今天我们就来说一下有关next数组求值的问题。  首先我们列出next的函数定义:  0,当j=1时 next[j]= Max{k|1  1 其他情况 ...
  • KMP模式匹配算法&next数组优化代码

    千次阅读 2018-09-17 13:49:15
    观察字串第一个字母a于后面的bcdex都不相等,而在①匹配可知,主和子串的前五位分别相等,意味着子串的首字母a不可能与主的第2位到第5位的字符相等,所以朴素算法中的②③斯⑤都是多余的。 例如: T[1]=a,T[2]...
  • next数组的求解方法是: 第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;...
  •  谈到next字符匹配,自然就想到kmp字符匹配算法,可以说next数组是kmp算法中的一种,当然小编觉得next比较简单首先写下来。  一、next数组是什么  next数组的理解之前,你要明白什么是kmp算法,kmp算法又称...
  • KMP入门级别算法详解--终于解决了(next数组详解)

    万次阅读 多人点赞 2017-08-16 22:55:36
    对于正常的字符模式匹配,主长度为m,子串为n,时间复杂度会...KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。 next数组详解 首先是理解KMP...
  • KMP算法是模式匹配专用算法。 它是在已知模式的next或nextval数组的基础上执行的。如果不知道它们二者之一,就没法使用KMP算法,因此我们需要计算它们。...KMP算法中有next数组和nextval数组之分。...
  • KMP算法详细讲解,next数组构造详解

    千次阅读 2017-08-11 19:46:49
    如题,给出两个字符s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置。 输入输出格式 输入格式: 第一行为一个字符,即为s1(仅包含大写字母) 第二行为一个字符,即为s2(仅包含大写字母) 输出...
  • private static int[] getNext(String s) { //传过来的是模式,返回的是next数组 int len = s.length(); //获取模式的长度 char[] p = s.toCharArray(); //把模式转换成char数组 int[] ne
  • 一、说明 (1)看到网上同一个字符求 next 数组的值有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1...
  • next数组介绍

    千次阅读 2015-09-13 20:49:48
    首先看看next数组值的求解方法例如:  模式 a b a a b c a c  next值 0 1 1 2 2 3 1 2     next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 180
精华内容 72
关键字:

串ababaaababaa的next数组