精华内容
下载资源
问答
  • kmp算法next数组
    2020-11-16 19:51:30

    next数组的求解方法是:

    第0位的next值为-1,第1位的next值为0,后面求解每一位的next值时,根据前一位进行比较。

    首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为0。

    如果数组的下标是从1 开始的 那么Next数组默认第0位和第1位 是0 和 1

    举例解释上边一段话的意思
    假设求串′ababaaababaa′的next数组

    模式串ababaaababaa
    下标01234567891011

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

    模式串ababaaababaa
    下标01234567891011
    next数组-10          

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

    模式串ababaaababaa
    下标01234567891011
    next数组-100         

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

    模式串ababaaababaa
    下标01234567891011
    next数组-1001        

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

    模式串ababaaababaa
    下标01234567891011
    next数组-10012       

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

    模式串ababaaababaa
    下标01234567891011
    next数组-100123      

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

    模式串ababaaababaa
    下标01234567891011
    next数组-1001231     

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

    模式串ababaaababaa
    下标01234567891011
    next数组-10012311    

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

    模式串ababaaababaa
    下标01234567891011
    next数组-100123112   

    9、第9位同理可得,为3

    模式串ababaaababaa
    下标01234567891011
    next数组-1001231123  

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

    模式串ababaaababaa
    下标01234567891011
    next数组-10012311234 

    11、最后,第11位同理可以得到next值位5

    模式串ababaaababaa
    下标01234567891011
    next数组-100123112345

    综上,串′ababaaababaa′的next数组为-1 0 0 1 2 3 1 1 2 3 4 5

    如果数组下标是从1开始 next数组从0 开始  结果就是上边的每个+1   0 1 1 2 3 4 2 2 3 4 5 6

    更多相关内容
  • 看了两天的KMP数组,终于理解了next数组怎么实现。图为本人理解,代码就不放了

    看了两天的KMP数组,终于理解了next数组怎么实现。图为本人理解,代码就不放了f0ea6b14dc1f4381b0d513d3706b0a75.png

     

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

    next数组求法

    ①next数组开始两个为固定值next[0] = 0;next[1] = 1;也有可能第一个值为-1,第二个为0(就是全部减一),具体情况具体分析。

    ②next数组可能下标从0开始,下面的例子中下标从1开始。

    ③从当前字符开始(不包含当前字符)往前找X个字符(不包含模式串第1个字符)形成子串S,S要求能从头和模式串完全匹配直到S结束,那么这个字符的next数组值为X+1。

    例1

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    例2

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 在网上有很多kmp算法的讲解,大概的框架讲的都还不错,但在next数组的讲解上,我觉得不是很清晰。 在学习KMP算法时,next数组的求解是它的精髓。 在博客中看了许多next数组的求法,推荐一篇kmp算法.我觉得写的非常好...


    在网上有很多kmp算法的讲解,大概的框架讲的都还不错,但在next数组的讲解上,我觉得不是很清晰。
    在学习KMP算法时,next数组的求解是它的精髓。
    在博客中看了许多next数组的求法,推荐一篇 kmp算法.我觉得写的非常好。

    理论基础

    前缀:字符串A和B,A=B+S,S非空,则B为A的前缀
    后缀:字符串A和B,A=S+B,S非空,则B为A的后缀
    PMT值:前缀集合和后缀集合的交集中,最长元素的长度
    prefix:每一个下标位置对应一个PMT值,组成的数组
    next:prefix向右移一个下标位置,组成的next数组

    部分匹配表的生成

    在学习next数组之前,我们先来看一下PMT值组成的数组,也就是kmp算法的部分匹配表,通过PMT值我们就可以知道子字符串应该如何移动,而不用进行整个回溯。
    如下图字符串BCADBCABCABCD为主串,字符串BCADBCD为副串,将副串与主串进行匹配,搜寻副串在主串中的位置。我们使用i来表示主串当前比对字符的位置,用j来表示副串当前比对字符的位置。我们从子字符串的j为0位置开始与主字符串进行一一比对,一直到副字符串的j为5位置副字符串和主字符串都是匹配的,在比对副字符串的j=6位置时即红色位置对应的位置时,不匹配。
    按照正常的思路,我们需要回溯,将i从6回溯到1的位置,将j从6返回到0的位置,再次进行匹配。将副字符串整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。
    在这里插入图片描述
    但是,我们在图中可以看出,当字符A与D不匹配时,你其实知道前面六个字符是"BCADBC"。即我们已经知道主串位置4前面不能与副串进行匹配,所以不用进行比对。而主串位置6前的BC两个字符与副串01位置的BC两个字符有重复,也不用与主串进行比对,所以我们可以将副串比对字符的位置移到2位置,即移到j=6元素对应的next值位置(下面又此字符串的next数组),与主串继续进行匹配。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率,即利用next数组,来提高匹配速度。
    在这里插入图片描述

    模式串BCADBCD
    PMT值0000120
    next值-1000012

    PMT值的生成

    在这里插入图片描述
    下标5:ABCABC
    下标5的前缀集合:A、AB、ABC、ABCA、ABCAB
    下标5的后缀集合:C、BC、ABC、CABC、BCABC
    最长交集元素长度:3(ABC)

    下标6:ABCABCD
    下标5的前缀集合:A、AB、ABC、ABCA、ABCAB、ABCABC
    下标5的后缀集合:D、CD、BCD、ABCD、CABCD、BCABCD
    最长交集元素长度:3(ABC)

    从下标最长交集元素长度,可推出PMT值,将PMT值右移一位,即可得到next数组。

    next数组的生成

    next数组的生成与上面经过PMT数组右移一位生成的相同。下面讲解next数组怎末生成
    next数组的生成,也就是子字符串与自己副本进行匹配对比的过程。
    我们将上面字符串叫做子字符串本体,下面字符串作为子字符串副本
    在这里插入图片描述
    先将子字符串复制一份,副本子字符串后移一位,进行按字符匹配。
    index0的位置,pmt为0,next的值为-1,也就是i=0,对应的j值,一般next数组第一位的值都是-1。
    在这里插入图片描述
    当index为1:将ij同时加一,此时子串字符B和复制字串字符A失配,next[1]值为当前j值,即next[1]值为0,j下标设置为下标0的next值-1,即j=next[0],j=-1代表着副本字串要向后移一位。
    在这里插入图片描述
    index2:当 j=-1时,将ij同时增加,即相当i+1,j=0,相当于副本字串右移一位,继续与字串继续进行比对,此时又失配,next[2]=j=0。而j=next[j]=-1,副本字串将将继续后移。
    在这里插入图片描述
    index3时: j=-1时,将ij同时增加,即相当i+1,j=0,相当于副本字串右移一位,继续与字串继续进行比对,此时子串本体对应字符和副本对应字符匹配,next[3]=j=0。继续匹配下一位。
    index4时:将ij同时增加,i=4,j=1,本体与副本继续对比,此时子串本体对应字符和副本对应字符适配,next[4]=j=1继续匹配下一位。
    index5时:将ij同时增加,i=5,j=2,本体与副本继续对比,此时子串本体对应字符和副本对应字符适配,next[5]=j=2继续匹配下一位。
    在这里插入图片描述
    index6时:将ij同时增加,i=6,j=3,本体与副本继续对比,此时子串本体对应字符和副本对应字符失配,next[5]=j=3,j=next[j]=0。按照此思路一直求解下去,自此next数组已经求解完毕。

    代码实现

    void getNext(char pattern[],int next[]){
    	next[0]=-1;
    	int i=0,j=-1;
        int pat_leng = strlen(pattern);
    	while(i<pat_leng){
    		if(j==-1) {
    			i++;
    			j++;
    		} else if(pattern[i] == pattern[j]){
    			i++;j++;
    			next[i]=j;
    		} else{
    			j=next[j];
    		}
    	}
    }
    

    主要讲解的是next数组求解的代码,按照上面图片的思路,如果j==-1的话,i和j同时加一,然后下一次循环判断是否相等,如果适配,即相等,i和j同时加一,检查下一位是否也相等。如果失配,即不相等的话,则将next[j]的值赋给j,继续进入循环。

    int search(char str[],char pattern[],int next[]){
    	int i=0,j=0;
    	int str_length = strlen(str);
    	int pattern_length = strlen(pattern);
    	while(i<str_length && j<pattern_length){
    		if( j==-1 || str[i] == pattern[j]){
    			++i;
    			++j;
    		} else 
    			j=next[j];
    	}
    	if(j == pattern_length)
    		return i-j;
    	else 
    		return -1;
    }
    

    搜索代码和暴力搜索字符串的思路基本一样,只不过将回退的代码换成了赋值next数组。

    int main()
    {
        char pattern[] ={"ABCABCD"};
        char str[]={"ABCABCCABCABCD"};
        int next[20]={0};
        getNext(pattern,next);
        printf("%d",search(str,pattern,next));
        return 0;
    }
    
    展开全文
  • KMP 算法 next 数组理解

    2020-08-25 18:24:30
    kpm算法有一步是求next数组,`next[i]`表示字符串`S[0...i]`中最大相同前后缀的索引。 比如字符串`abcdab`,整个字符串的最大相同前后缀相是`ab`,那么`next[5]=1`。 实现 function next($s) { $next = array_...
  • 关于KMP算法next数组的改进——nextval数组
  • 提到KMP算法,很多人都觉得很困难,困难之处就在next数组部分,下面我来详解一下这部分的运行操作 next数组需要研究子串的前缀和后缀的重复部分,我们假设有两个完全相同的模式串,一个叫做伪主串,另一个叫伪模式串...
  • KMP算法next 数组求解

    2021-08-09 18:46:26
    KMP算法next数组求解 ** 要求那个next数组(有些叫next-val数组): 1.必须先求模式串S 每一个字符前面的那个字符串的最大公共前后缀长度,将这一系列长度存成一个数组,求出来的每个长度其实就是和模式串每一个对应...
  • 超详细理解:kmp算法next数组求解过程和回溯的含义

    万次阅读 多人点赞 2017-11-14 15:59:44
    前言KMP算法是用来求一个较长字符串是否包含另一个较短字符串的算法。具体算法下一篇写吧,这篇主要解释next数组的求解。
  • KMP算法PMT数组与next数组构造解释

    千次阅读 2021-12-08 20:07:35
    KMP算法是用于搜索子串的经典算法,其中重点就在于利用了next数组减少了很多重复的搜索,这里不细讲KMP算法是怎么进行搜索的,我尽可能地将next的数组构造中的一些当时令我困惑的问题讲解清楚。     2. ...
  • KMP算法
  • 串的模式匹配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数组部分难点的一些理解求next值的代码 部分难点的一些理解 求next值的代码 Void get_next(string st,int next[]) { }
  • 手算KMP算法next数组

    千次阅读 2020-07-20 22:49:25
    next数组中第一位写0,第二位写1 。求解后面每个元素的next值时,将该元素前一个元素next值所对应下标的元素进行比较,如果相同,则将前一元素next值+1作为当前元素的next值;否则,则将前一元素next值所对应下标的...
  • KMP算法(kmp) next数组算法解析

    千次阅读 2021-04-03 10:39:53
    KMP算法的精髓在于next数组,首先解释next数组中的值代表的意义: eg:a b a c next【4】指在第四元素之前的三个元素中,前缀和后缀相同的最大长度为1+1=2, 所以next【4】=2; (关于前缀和后缀的问题,CSDN有很多...
  • 解决问题: 前缀表和next数组的关系 为什么有些next数组是0,1开头,而有些next数组是-1,0开头 如何计算KMP算法中的next数组 注:本文不讲解KMP算法的实现,只涉及next数组的计算
  • 在复习数据结构课程的过程中 对kmp算法next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
  • 三、求next数组 1、最长公共前后缀 假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj,我们就说在P串中有一个最大长度为k+1的公共前后缀。 2、如何寻找前后缀??? 找前缀时,...
  • KMP算法next数组

    2022-05-30 11:23:03
    手写kmp算法讲解的比较多,但是对求next的代码却少有解释,因此记录一下kmp算法next数组的代码解释。
  • KMP算法作为经典的字符串匹配算法,确实很难理解,我尽量解释清楚我的理解。 因为该算法大体上可分为两块(kmp的原理,next数组的推导),该博客将详细分析next的数组的推导。(ps:大约有两种next数组的写法,我使用的...
  • KMP算法next数组求解

    2022-03-09 17:58:24
    前缀与后缀: 首先,理解什么是前缀什么是后缀。 前缀:包含首字母,不包含尾字母的所有子串 ...而KMP算法的核心next数组表示的就是子串的最长相等前后缀的长度 比如字符串"abaabac" a -- 0 ab -- 0
  • kmp算法next数组理解

    2018-12-09 11:23:51
    kmp算法的核心是next数组next数组利用回溯的思想,当字符不匹配时,回退到前面已经匹配成功的下一个位置。  最开始呢,我其实真的很不理解next数组,我只知道回退到最大前后缀的子串的长度,但是next数组和...
  • 1、基本概念 前缀:包含首字母,不包含尾字母的所有子串;... //移动主串 //而next[j]一般指前j个字母拥有的最大公共前后缀强度 计算D[ ] P串错开匹配 KMP算法之求next数组代码讲解_哔哩哔哩_bilibilihttps://...
  • KMP算法next数组的手工计算方法

    千次阅读 2018-09-02 00:08:06
    KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体...
  • KMP算法next数组详解

    2022-01-02 16:44:57
    KMP算法主要是用来求解子串在主串中第一次出现的位置,并返回这个子串的位置的一种提高效率的方法。在讲解KMP算法之前,我们先来看看求子串在主串中位置的一般解法,即暴力解法。 1.暴力解法 public static ...
  • KMP算法&next数组详解

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

    千次阅读 多人点赞 2020-12-03 22:17:02
    KMP算法next数组详解 KMP算法实现原理 KMP算法是一种非常高效的字符串匹配算法,下面我们来讲解一下KMP算如何高效的实现字符串匹配。我们假设如下主串和模式串: int i;//i表示主串的下标 int j;//j表示模式串的...
  • kmpnext数组的应用

    2022-02-11 11:58:34
    首先加深以下对next数组的理解(kmp算法见基础算法专栏),next它的核心是这个公式: next[j] = k; 它的含义是在模式字符串p中,[ 0 , j )这一子串的最长匹配数(前缀与后缀相同的最长个数)为k,所以若在p[j] 处...
  • KMP 算法中的 next 数组

    2022-03-28 21:47:25
    KMP 算法中对 next 数组的理解 next 数组的意义 此处 next[j] = k;则有 k 前面的浅蓝色区域和 j 前面的浅蓝色区域相同; next[j] 表示当位置 j 的字符串与主串不匹配时,下一个需要和主串比较的字串位置在 next[j] ...
  • KMP算法next数组实现

    万次阅读 2021-04-20 16:38:28
    KMP算法 for leetcode 实现strStr() 前不久打虎符CTF的qual时候做过一道redemption_...kmp的关键就是如何得到next数组,LeetCode里面的推导结合代码看的话会比较清楚。我在代码里加了注释,配合LeetCode的官方题解,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,821
精华内容 8,728
关键字:

kmp算法next数组