-
2022-03-24 17:42:09
求串′ababaaababaa′的next数组
模式串 a b a b a a a b a b a a 下标 1 2 3 4 5 6 7 8 9 10 11 12 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数组为
0 1 1 2 3 4 2 2 3 4 5 6 更多相关内容 -
next数组的计算方式
2021-11-17 16:36:57i 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] 分别为1和2、3、4、5。
总结:
1、next数组首个位置数值为定值-1
2、next[i]的值是看在s[i]之前的字符串中重复的子串长度(1、不统计第i位置的字符2、两个子串一个必须从首位置开始,另一个必须从尾位置结束)
-
数据结构C语言---模式串next数组和nextval数组的生成
2020-11-03 16:22:45next数组一、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
方法一 前缀后缀匹配
- 前缀和后缀进行比较,如果前缀和后缀没有相同前缀,则为0+1,如果相同,则相同的字符个数+1;
- 前缀取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
-
数据结构 串——next数组、nextval数组
2022-03-02 18:00:40//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]; } } }
这些代码很好看懂,却没办法轻易‘看’懂。其实在看到这段代码的时候,我满头问号,直呼凭什么,自己试着琢磨了一段时间,最后还是去搜了相关的讲解视频。
其实画一个图,一切的问题就会变得简单很多。
-
串——求解next数组和nextval数组
2021-05-23 01:52:25求解nextnext数组的求解方法:首先第一位的next值直接给0,第二位的next值直接给1,后面求解每一位的next值时,都要前一位进行比较。首先将前一位与其next值的对应位进行比较,若相等,则该位的next值就是前一位的... -
求next数组详解
2020-05-20 00:20:37next数组详解思路前缀、后缀、部分匹配值部分匹配(Partial Match,PM)表next数组求解方法代码实现 前缀、后缀、部分匹配值 "前缀"指除了最后一个字符以外,字符串的所有头部组合; "后缀"指除了第一个字符以外,... -
字符串之KMP算法求解next数组(C语言)
2021-06-13 15:10:56next数组的作⽤:当模式串的第j个字符失配时,从模式串的第next[j]的继续往后匹配。 ①、任何模式串都一样,第一个字符不匹配时,只能匹配下一个子串,<font color='red'>next[1]都无脑写0 ②、任何模式串都一样,第... -
数据结构-串-KMP算法详解(Next数组计算)(简单易懂)
2022-04-11 20:38:24数据结构kmp算法 next数组计算 如何使用next匹配 -
KMP算法中模式串移动next数组的计算
2020-10-21 20:36:49题目描述 字符串的子串定位称为模式...请参考教材next数组的计算公式与算法,编程实现之。 输入 一个模式串,仅由英文小写字母组成。长度不大于100。 输出 输出模式串对应的移动数组next。每个整数后跟一个空格。 样 -
KMP算法初始化模式串的next数组
2020-05-14 17:03:52在使用KMP算法处理字符串查找问题的过程当中,可以利用模式串本身的对称性,在移动模式串的时候,尽量多的往后移动,减少无用的查找过程,而模式串本身的对称性一般是保存在一个next数组里面的,下面来讨论下怎么... -
串′ababaaababaa′的next数组(求next数组思路与实例)
2018-06-17 16:53:46首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值... -
KMP算法,手动计算next数组和nextval数组
2021-10-24 21:59:02文章目录前言一、求模式串(子串)的next数组与nextval数组next数组的计算nextval数组的计算2.第一轮匹配:3.第二轮匹配:代码待续 前言 KMP算法:主串与模式串的匹配过程 一、求模式串(子串)的next数组与... -
next数组求解详解
2017-08-20 20:52:59next数组求解详解,以串'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 开头看... -
(数据结构期末复习)求字符串的next数组和nextval数组的值
2021-01-21 23:19:15这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正! 《数据结构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:55KMP算法的核心,是一个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:02KMP算法之next数组详解 KMP算法实现原理 KMP算法是一种非常高效的字符串匹配算法,下面我们来讲解一下KMP算如何高效的实现字符串匹配。我们假设如下主串和模式串: int i;//i表示主串的下标 int j;//j表示模式串的... -
如何理解next数组和获取
2020-04-16 10:26:58该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。 提取加速匹配的信息 上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效... -
一个关于字符串前后缀的神奇数组:next 数组
2018-08-18 21:25:00关于next数组最好能结合图片来理解,有很多相关的博客,这里不再引述,本文只总结核心的内容。此外next数组有两个版本,本文用的是next[0]=-1的版本,两个版本没有本质区别,选择一个记忆即可,但选了一个后就把另一... -
求字符串‘abaabcac’的next数组和nextval数组
2020-03-06 17:53:52今天刷到一个笔试题,求一个字符串在KMP算法下的next数组 几番百度和看题解,居然大多数的题解都有毛病被一顿吐槽 最后,通过一张动图搞懂了计算的原理 如下: 本图来自这个博客 正如下面评论说的,文章写得可能不... -
next数组和nextval数组值
2021-08-27 18:57:37next数组的求解方法是:第一位的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...