精华内容
下载资源
问答
  • 2022-03-24 17:42:09

    求串′ababaaababaa′的next数组

    模式串ababaaababaa
    下标123456789101112

    next[1] = 0

    next[2] = 1

    (这两个值是约定的)

    next[3]: "ab"没有相同的前缀和后缀,所以模式串又得从头开始匹配,因此next[3] = 1

    next[4]: "aba"的最长公共串是“a”,所以按照下面这个例子,虽然第四位没有匹配上,但是前三位匹配上了,并且第一位和第三位相同,因此可以将模式串整体向右移动,直到将原来的第一位移到原来的第三位上,继续进行匹配,而原来模式串指针指着的第四位现在指向第二位了,因此next[4] = 2

    abacfffffffffff...

    ababaaababaa

        ababaaababaa

    next[5]: "abab"的最长公共串是“ab”,next[5] = 3

    ababcfffffff...

    ababaaababaa

        ababaaababaa

    next[6]: "ababa"最长公共串是“aba”,next[6] = 4

    ababacfffffff...

    ababaaababaa

        ababaaababaa

    next[7]: "ababaa"最长公共串是“a”,next[7] = 2

    ababaacffffff...

    ababaaababaa

               ababaaababaa

    next[8]: "ababaaa"最长公共串是“a”,next[8] = 2

    next[9]: "ababaaab"最长公共串是“ab”,next[9] = 3

    next[10]: "ababaaaba"最长公共串是“aba”,next[10] = 4

    next[11]: "ababaaabab"最长公共串是“abab”,next[11] = 5

    next[12]: "ababaaababa"最长公共串是“ababa”,next[12] = 6

    next数组为

    011234223456
    更多相关内容
  • next数组计算方式

    2021-11-17 16:36:57
    i 0 1 2 3 4 5 6 7 8 9 10 11... 总结: 1、next数组首个位置数值为定值-1 2、next[i]的值是看在s[i]之前的字符中重复的子串长度(1、不统计第i位置的字符2、两个子串一个必须从首位置开始,另一个必须从尾位置结束)

    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[i]的值主要是看s[i]之前的字符串中重复的子串长度。next[0] = -1,定值。

    next[1]是看s[1]之前的字符串“a”中重复的子串长度为0,故next[1] = 0

    next[2]是看s[2]之前的字符串“ab”中重复的子串长度为0,故next[2] = 0

    next[3]是看s[3]之前的字符串"aba"中重复的子串长度,s[0]s[2]重复,长度为1,故next[3] = 1

    next[4]是看s[4]之前的字符串"abab"中重复的子串长度,s[01]s[23]重复,长度为2,故next[4] = 2

    next[5]是看s[5]之前的字符串"ababa"中重复的子串长度,s[012]s[234]重复,长度为3,故next[5] = 3

    next[6]是看s[6]之前的字符串"ababaa"中重复的子串长度,s[0]s[5]重复(因为多了一个a,无法找到长度为3的重复字符串,这只能是s[0]s[5]重复),长度为1,故next[6] = 1

    同样的,求next[7]next[8]next[9] next[10] next[11] 分别为12345

    总结:

    1next数组首个位置数值为定值-1

    2next[i]的值是看在s[i]之前的字符串中重复的子串长度(1、不统计第i位置的字符2、两个子串一个必须从首位置开始,另一个必须从尾位置结束)

    展开全文
  • next数组

    一、next数组(简单易懂)

    next函数值仅取决于模式串本身,与主串无关

    next数组的生成这里有两种方式:
    1.前缀后缀匹配
    2.字符串下标匹配
    以一个数组为例:
    a b a b a a a b a b a a 
    我们要生成这个模式串的next数组,那么首先第一件事就是为这些字符标号,
    如下;
    
      序号j: 1 2 3 4 5 6 7 8 9 10 11 12
    模式串s: a b a b a a a b a b  a  a
    

    方法一 前缀后缀匹配

    1. 前缀和后缀进行比较,如果前缀和后缀没有相同前缀,则为0+1,如果相同,则相同的字符个数+1;
    2. 前缀取s[n]之前字符的n-2位,后缀取s[n]之前n-1字符后面的后n-2位。
      序号j: 1 2 3 4 5 6 7 8 9 10 11 12
    模式串s: a b a b a a a b a b  a  a
     next[]: 0 1
     1.next[1],next[2]无论是什么模式串数组,永远都是0和1。
     
     2.next[3]:如上,序号j[3]对应的模式串s[3],那么我们就看模式串s[3]前面的
     字符即可,即为a b,那么s[3]的前缀为a,后缀为b,a和b不相同,则next[3]为0+1=1;
     
     3.next[4]:序号j[4]对应的s[4],找s[4]的前面字符,为a b a,字符前缀为a、ab;
     后缀为ba, a;有1个相同字符,则next[4]=1+1=2;
    
     4.next[5]:序号j[5]对应的s[5],找s[5]的前面字符,为a b a b,字符前缀为a、ab
     aba三个,后缀为bab、ab、b三个,进行比较,有字符串ab相同,则next[5]=2+1=3
    
     以此类推......
    
     5.next[12]:序号j[12]对应的模式串字符为s[12],取前n-1个字符,为a b a b a a a b a b a,前缀为:ababaaabab,后缀为babaaababa.
     可看出前缀中 ababa与后缀中ababa5个字符相同,则next[12]=5+1=6;
    

    最终生成的next字符串为:

        j: 1 2 3 4 5 6 7 8 9 10 11 12
        s: a b a b a a a b a b  a  a
     next: 0 1 1 2 3 4 2 2 3 4  5  6
    

    方法二 字符串下标匹配

      序号j: 1 2 3 4 5 6 7 8 9 10 11 12
    模式串s: a b a b a a a b a b  a  a
     next[]: 0 1 1 2 3 4 2 2 3 4  5  6
     1.next[1],next[2]无论是什么模式串数组,永远都是0和1。
     
     2.next[3]:我们要生成next[3]的值,就要先看前一位s[2]对应的next值为1,那么
     以对应的next值1为下标,s[1]与s[2]比对,不相同,则next[3]为0+1=1。
     
     3.next[4]:要生成next[4],首先要看前一位s[3]对应的next值为1,则以对应的
     next值为下标,s[3]不变,s[1]为a,s[3]也为a,相同,则以s[3]下标1进行加一,为
     1+1=2,所以,next[3]=2;
     
     4.next[5],next[6]:同理。next[5]=3,next[6]=4
     
     5.next[7]:到这就有问题了,前一位s[6]所对应的next下标为4,所以,s[6]和s[4]对比,不相同!那么,继续看s[4]所对应的next下标,
     为2,s[6]不动,永远作为对比方,与s[4]对应next下标数字为序号再次进行对比,以此类推,s[2]=b,
     s[6]=a,不相同!继续操作,s[2]的next值为1,以是s[1]为下标,继续对比,s[1]=s[6]=a.到此为止,next[7]的值为s[2]的next值+1,为2.
     
     6.后面同理。
     
    

    二、nextval(有手就行)

    这里我们只介绍最简单的生成nextval数组的方法,nextval数组第一个字符永远为0。
    既然我们上面生成了next数组,nextval数组直接通过next数组便可生成。
    若不同,填入next的值;若相同,填入该值对应的序号的nextval.

       序号 : 1 2 3 4 5 6 7 8 9 10 11 12
     模式串s: a b a b a a a b a b  a  a
      next[]: 0 1 1 2 3 4 2 2 3 4  5  6
     nextval: 0 
     
     1.nextval[1]=0,默认值
     2.nextval[2]:s[2]对应的next值为1,则以1为下标s[1],与s[2]进行对比,不相同,
     则将s[2]对应的next值直接下发到nextval,nextval[2]=next[2]=1;
     3.nextval[3]:s[3]对应的next值为1,则以1为下标,与s[3]进行对比,相同,则nextval[3]=nextval[1]=0;
     4.nextval[4]:s[4]对应的next值为2,则以2为下标,与s[4]进行对比,相同,则nextval[4]=nextval[1]=0;
     5.依次同理.....
     6.nextval[12]:s[12]对应的next值为6,则s[6]与s[12]对比,相同,则nextval[12]=nextal[6]=4;
     
     最终生成的nextval为:
       序号 : 1 2 3 4 5 6 7 8 9 10 11 12
     模式串s: a b a b a a a b a b  a  a
      next[]: 0 1 1 2 3 4 2 2 3 4  5  6
     nextval: 0 1 0 1 0 4 2 1 0 1  0  4
    
    展开全文
  • //s主,t字串,pos初始为1 //返回第pos个位置之后有字串,无则返回0 int Index(String* s, String* t, int pos) { if (pos<1 || pos>s->length - t->length + 1) { printf("输入有误"); } int i ...
    //朴素算法
    //s主串,t字串,pos初始为1
    //返回第pos个位置之后有字串,无则返回0
    int Index(String* s, String* t, int pos) {
    	if (pos<1 || pos>s->length - t->length + 1) {
    		printf("输入有误");
    	}
    	int i = pos; //i用于主串的位置
    	int j = 0;   //j用于子串的位置
    	while (i <= s->length && j <= t->length) {
    		if (s[i - 1] == t[j]) {
    			i++;
    			j++;
    		}
    		else {
    			i = i - j + 1;
    			j = 0;
    		}
    	}
    	if (j == t->length) {
    		return i - t->length;
    	}
    	else {
    		return 0;
    	}
    }
    
    
    //next数组
    int get_next(String* t, int* next) {
    	int i, j;
    	i = 1;
    	j = 0;
    	next[1] = 0;
    	while (i < t->length) {
    		if (j == 0 || t[i] == t[j]) {
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else {
    			j = next[j];
    		}
    	}
    }
    
    
    //nextval数组
    void get_nextval(String* t, int* nextval) {
    	int i, j;
    	i = 1;
    	j = 0;
    	nextval[1] = 0;
    	while (i < t->length) {
    		if (j == 0 || t[i] == t[j]) {
    			++i;
    			++j;
    			if (t[i] == t[j]) {
    				nextval[i] = nextval[j];
    			}
    			else {
    				nextval[i] = j;
    			}
    		}
    		else {
    			j = nextval[j];
    		}
    	}
    }

    这些代码很好看懂,却没办法轻易‘看’懂。其实在看到这段代码的时候,我满头问号,直呼凭什么,自己试着琢磨了一段时间,最后还是去搜了相关的讲解视频。

    其实画一个图,一切的问题就会变得简单很多。 

     

    展开全文
  • 求解nextnext数组的求解方法:首先第一位的next值直接给0,第二位的next值直接给1,后面求解每一位的next值时,都要前一位进行比较。首先将前一位与其next值的对应位进行比较,若相等,则该位的next值就是前一位的...
  • next数组详解

    千次阅读 2020-05-20 00:20:37
    next数组详解思路前缀、后缀、部分匹配值部分匹配(Partial Match,PM)表next数组求解方法代码实现 前缀、后缀、部分匹配值 "前缀"指除了最后一个字符以外,字符的所有头部组合; "后缀"指除了第一个字符以外,...
  • next数组的作⽤:当模式的第j个字符失配时,从模式的第next[j]的继续往后匹配。 ①、任何模式都一样,第一个字符不匹配时,只能匹配下一个子串,<font color='red'>next[1]都无脑写0 ②、任何模式都一样,第...
  • 数据结构kmp算法 next数组计算 如何使用next匹配
  • 题目描述 字符的子串定位称为模式...请参考教材next数组计算公式与算法,编程实现之。 输入 一个模式,仅由英文小写字母组成。长度不大于100。 输出 输出模式对应的移动数组next。每个整数后跟一个空格。 样
  • KMP算法初始化模式next数组

    千次阅读 2020-05-14 17:03:52
    在使用KMP算法处理字符查找问题的过程当中,可以利用模式本身的对称性,在移动模式的时候,尽量多的往后移动,减少无用的查找过程,而模式本身的对称性一般是保存在一个next数组里面的,下面来讨论下怎么...
  • 首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值...
  • 文章目录前言一、求模式(子串)的next数组与nextval数组next数组计算nextval数组的计算2.第一轮匹配:3.第二轮匹配:代码待续 前言 KMP算法:主与模式的匹配过程 一、求模式(子串)的next数组与...
  • next数组求解详解

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

    万次阅读 多人点赞 2019-01-27 16:26:48
    在牛客网刷题遇到了求next数组的题型,结果在学校学的没有牢记,做错了,还是要多刷题做总结啊。 我们先口述说明一下next数组的求解方法: 我们能确定next数组第一二位一定分别为0,1,后面求解每一位的next值时,...
  • next数组两种求法

    万次阅读 多人点赞 2018-08-22 15:03:37
    (1)看到网上同一个字符求 next 数组的值有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1 开头看...
  • 这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正! 《数据结构C语言版第2版》的课后习题里有这两道题(答案是CA) 书上求next数组和nextval数组的代码如下: ...计算ababaaababaa的next数组: ne
  • 字符匹配问题——next数组计算

    千次阅读 2017-08-18 16:19:44
    在KMP算法中,最关键的就是求解next数组了。那么如何快速求解next数组呢? 已知模式:A B C D A B D D A 其next数组:0 0 0 0 120 0 1 那么是如何求证出来的呢? 首先字符从左至右遍历。 第一个字符A的next...
  • KMP算法中计算next数组的代码

    千次阅读 2020-11-04 17:24:55
    KMP算法的核心,是一个next数组。 在KMP算法的众多实现中,有许多种定义next数组的方式。所以在使用和查看别人代码时,要特别注意KMP算法的next数组的定义,以免发生混淆。如:严蔚敏《数据结构》将模式下标从1...
  • 字符匹配:求给定字符next数组以及KMP算法

    千次阅读 多人点赞 2017-03-26 16:25:15
    理解字符next数组next数组值的概念涉及到字符匹配的问题,比较抽象,先介绍一些预备知识: 1. 主和模式 例如我们想知道一个字符是否包含另一个字符时,如S="bbc abcdab abcdabcdabde"中是否...
  • KMP算法之next数组详解

    千次阅读 多人点赞 2020-12-03 22:17:02
    KMP算法之next数组详解 KMP算法实现原理 KMP算法是一种非常高效的字符匹配算法,下面我们来讲解一下KMP算如何高效的实现字符匹配。我们假设如下主和模式: int i;//i表示主的下标 int j;//j表示模式的...
  • 该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主指针的回溯,从而使算法效率有了某种程度的提高。 提取加速匹配的信息  上面说道 KMP 算法主要是通过消除主指针的回溯来提高匹配的效...
  • 关于next数组最好能结合图片来理解,有很多相关的博客,这里不再引述,本文只总结核心的内容。此外next数组有两个版本,本文用的是next[0]=-1的版本,两个版本没有本质区别,选择一个记忆即可,但选了一个后就把另一...
  • 求字符‘abaabcac’的next数组和nextval数组

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

    千次阅读 多人点赞 2021-08-27 18:57:37
    next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;...
  • KMP 算法以及 next 数组计算

    千次阅读 2018-08-23 17:01:26
    看本文的同志们需要注意的是,本文没有按照一般的套路来介绍KMP算法,而是侧重于介绍KMP算法为什么这样做,关于KMP算法和next非常值得一看的博客推荐如下: https://www.cnblogs.com/tangzhengyue/p/4315393.html ...
  • KMP算法&next数组详解

    千次阅读 2020-10-28 13:13:12
    文章目录KMP算法详解前言一、示例二、用朴素的字符匹配算法三、KMP算法实现1、KMP算法思路2、next数组的本质3、next数组带入思路实现4、next数组的求法4、代码实现C语言实现Java语言实现 前言 KMP算法是目前字符...
  • KMP算法--求next数组

    2021-05-28 20:43:06
    最近在学数据结构,三天看了180页pdf,佩服我自己,当然最主要的还是我...next数组,我相信学过或者了解过KMP算法的对它一定不陌生,可以这样说,整个LMP算法的精髓就在于对next数组的求解。我将用我所看的文章图片或者
  • KMP算法next数组详解

    2021-05-22 03:22:39
    ==> 学习汇总(持续更新)==> 从零搭建后端基础设施系列(一)-- 背景介绍KMP算法的核心就是利用已匹配...next数组生成的步骤:假设模式是“ABABABB”**前缀:**除最后一个字符外,例如,A、AB、ABA、ABAB、ABAB...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 259,177
精华内容 103,670
关键字:

如何计算串的next数组