精华内容
下载资源
问答
  • KMP算法NEXT数组计算方法

    万次阅读 多人点赞 2017-03-05 23:24:10
    KMP算法: 关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。 个人对于Next()函数...

    KMP算法:

    关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。


    个人对于Next()函数的理解:

    一:思路概括:我语文不太好可以忽略,可以先看手工实现

    1,把将要进行next计算的字符串S分成 k ,j 前后两串,k代表前串开头所在的序号,j代表后串开头所在的序号,起始的时候j=1,k=0。

    2,我们比较一下前串 后串是否相等,要怎么比较呢,肯定是比较S[j]==S[k],如果相等,那么next[j+1]=k+1,然后j++,k++。

    关键就是理解这个next[j+1]=k+1(为什么k+1,由于下标是从0开始?):简单说就是S串中的第j+1个字符的next函数值由他前面的字符与前串相等的个数来决定,就是说串中的第j+1个字符的next函数值,是由他前面的字符串决定的

    3,当S[j]!=S[k],即不相等的时侯,那么j不动,k返回到开头(因该是next[k]位置,便于理解先假设是返回k=0处),即从头比较S[0]与S[j],S[1]与S[j+1]

    例如:第 j+1 个字符的next函数值next[j+1]等于3,意味着 他的前三个字符串,S[j-2]S[j-1]S[j] =S[0]S[1]S[2]

    二:手工实现理解

    例1

             

    序号

    0

    1

    2

    3

    4

    5

    6

    7

    8

    子串

    a

    b

    c

    a

    a

    b

    c

    b

    a

    Next值

    -1

    0

    0

    0

    1

    1

    2

    3

    0


    1,第一个字符的next值令为-1。令第二个字符b的next值为0,初始k=0,j=1, 比较S[k] 和S[j]

    2,比较S[0] !=S[1]  所以  j++ k不变 next[j=2]=0

    3,比较S[0] !=S[2]  所以  j++ k不变 next[3]=0

    4,比较S[0]  ==S[3]   所以  j++,k++, next[4]=k=1

    5,k=1了 所以比较S[1] !=S[4],k返回到next[k]位置,即k=next[1]=0,然后比较S[k=0] == S[4] 所以 j++ ,k++ ,next[5]=k=1

    6,比较S[1] ==S[5]   所以 j++ ,k++ ,next[6]=k=2

    7,比较S[2] ==S[6]   所以 j++ ,k++ ,next[7]=k=3

    8,比较S[3] !=S[7]     所以k返回到next[k=3]位置,即k=next[3]=0,然后比较S[k=0] != S[7] 所以 j++ ,不变k=0不变,next[8]=k=0

    完毕

    可以轻松的发现,S[j]的比较,决定了字符 S[j+1 ] 的next函数值


    例二:在例一中,每次不相等时返回的都是k=next[k]=0,都是返回到了开头,我们看一个不是返回到开头0的情况:

    序号

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    子串

    a

    a

    b

    c

    a

    a

    a

    b

    a

    a

    c

    Next值

    -1

    0

    1

    0

    0

    1

    2

    2

    3

    1

    2



    从 j=5,k=1的时候开始

    5,比较 S[1] == S[5] 所以 j++,k++,next[j+1=6]=k=2

    6,比较S[2] != S[6] 所以 k返回到next[k=2]位置,即k=next[2]=1,然后比较S[k=1]  == S[6] 所以 j++ ,k=1+1=2,next[7]=k=2

    …………

    因此,我们发现K的退回 是退回到next[k]的位置 即S[j]!=S[k]时,k=next[k]


    二:getNext函数实现代码如下


    void getNext(char *p,int *next)  
    {  
        int j,k;  
        next[0]=-1;  
        j=0;  //后串起始位置,一直增加 
        k=-1;  //k==-1时,代表j++进入下一轮匹配,k代表前串起始位置,匹配失败回到-1 
        while(j<strlen(p)-1)  
        {  
            if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k],next[j+1]=k+1;  
            {  
                ++j;  
                ++k;  
                next[j]=k;  
            }  
            else                   //p[j]!=p[k],k=next[k]  
                k=next[k];  
        }  
    }  


    KMP算法那完整实现代码如下


    #include<stdio.h>
    #include<string.h>
    	int next[30];
    void getNext(char *p,int *next)  
    {  
        int j,k;  
        next[0]=-1;  
        j=0;  //后串起始位置,一直增加 
        k=-1;  //k==-1时,代表j++进入下一轮匹配,k代表前串起始位置,匹配失败回到-1 
        while(j<strlen(p)-1)  
        {  
            if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k],next[j+1]=k+1;  
            {  
                ++j;  
                ++k;  
                next[j]=k;  
            }  
            else                   //p[j]!=p[k],k=next[k]  
                k=next[k];  
        }  
    }  
    
    int my_kmp(char* s1,char* key){
    	int i=0;
    	int j=0;
    	int l1=strlen(s1);
    	int l2=strlen(key);
    	while((i<l1)&&(j<l2)){
    		if(j==-1||s1[i]==key[j]){
    			i++;
    			j++;
    		}
    		else{
    			//i=i-j+1;j=0;
    			j=next[j];
    		}
    	}
    	if(j>=l2)return i-l2;
    	else return 0;
    } 
    int main(){
    	char* s="aabcaaabaac";
    
    	getNext(s,next);
    
    	printf("%d",1+my_kmp("aabaabbccaabbaaccaaabccbcaacccb",s));
    }


    展开全文
  • KMP算法next数组计算方法的优化

    万次阅读 2014-12-26 11:34:48
    KMP算法的原理就是利用相匹配的前缀子串与后缀子串,来确定失配时下次对齐的位置; 其中最关键的就是next数组的确立; 数据结构课本上经典的例子: void getNext(const char *pStr, int *nextArr) { int i = 0, k ...

    KMP算法的原理就是利用相匹配的前缀子串与后缀子串,来确定失配时下次对齐的位置;

    其中最关键的就是next数组的确立;

    数据结构课本上KMP算法next数组计算经典的例子:

    void getNext(const char *pStr, int *nextArr)
    {
    	int i = 0, k = -1, pLen = strlen(pStr);
    	nextArr[i] = k;
    	int mLen = pLen - 1;
    	while (i < mLen)
    	{
    		if (k == -1 || pStr[i] == pStr[k])
    		{
    			nextArr[++i] = ++k;
    		}
    		else k = nextArr[k];
    	}
    }

    而这个KMP算法next数组计算只关注了前k-1个字符中,前后匹配的子串,没有利用到当前失配的字符;

    比如:ABACA,当第2个A失配时,说明被匹配串的当前位置的字符必定不等于A,所以将第0位对齐到此位也必定失配,所以应该继续回溯到第0位失配时所需要对齐的位,这里也就是-1;

    这个"必定不等于(!=)"是可以被利用的!我们对KMP算法next数组计算的优化正是基于此;

    废话不多说,下面是优化后的KMP算法next数组计算与注释:

    //优化过后的next数组求法
    void getNext(const char *pStr, int *nextArr)
    {
    	int j = 0, j_next = -1, pLen = strlen(pStr);
    	nextArr[j] = j_next;//此处第0位失配,则对齐第-1位;
    	int mLen = pLen - 1;
    	while (j < mLen)
    	{
    		//基于第j位与第j_next已经相等(或者j_next为-1)
    		//广义地将空字符(pStr[-1])看做可以与任意字符相等,这样很益于理解
    		//求下一个j失配时的对齐位
    		if (pStr[++j] != pStr[++j_next])
    		{
    			//因为(自增++之后)pStr[j]与pStr[j_next]不相等
    			//所以此时pStr[j]失配后,可以用pStr[j_next]来试试,所以nextArr[j] = j_next;
    			nextArr[j] = j_next;
    			//因为此时pStr[j]与pStr[j_next]不相等
    			//所以回溯取pStr[j_next]失配时的对齐位pStr[nextArr[j_next]]
    			//直到相等为止
    			while (j_next != -1 && pStr[j] != pStr[j_next]) j_next = nextArr[j_next];
    		}
    		//这里就是优化点
    		//因为(自增++之后)pStr[j]与pStr[j_next]相等
    		//所以pStr[j]失配后,pStr[j_next]也必定失配
    		//故丢弃pStr[j_next],再取pStr[j_next]失配时的对齐位pStr[nextArr[j_next]]
    		//也即nextArr[j] = nextArr[j_next];
    		else nextArr[j] = nextArr[j_next];
    	}
    }

    给个无注释纯净版的(KMP算法next数组计算):

    void getNext(const char *pStr, int *nextArr)
    {
        int j = 0, j_next = -1, pLen = strlen(pStr);
        nextArr[j] = j_next;
        int mLen = pLen - 1;
        while (j < mLen)
        {
            if (pStr[++j] != pStr[++j_next])
            {
                nextArr[j] = j_next;
                while (j_next != -1 && pStr[j] != pStr[j_next]) j_next = nextArr[j_next];
            }
            else nextArr[j] = nextArr[j_next];
        }
    }

    欢迎拍砖与指正!


    展开全文
  • 串的模式匹配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[]数组的求解总结

    步骤(1)

    初始化

    next[1]=0  

    next[2]=1;

    步骤(2)求next[j],令k=next[j-1]
    步骤(3)

    S[j-1]    S[k]  比较大小

             = ,   next[j]=k+1

             != ,  k=next[k], k!=0, 返回(3);

             k= 0,next[j]=1

    根据以上方法,在具体习题中,需要建立一个表格,即可解决此类问题。

    j(字符串位序)12345....
    S[j]  (字符串对应位序的字符)..................
    next[j]  (下一次需要开始匹配的字符位序)..................

    具体计算过程

    下面是结合具体例题的实际计算过程:

    例题:在kmp算法中进行模式匹配,模式串为“ababaaababaa”的next数组值为(   )

    首先建立表格如下:

    j123456789101112
    S[j]ababaaababaa
    next[j]

    然后按照方法进行计算next(j)数组:   

            1),初始化:next[1]=0     next[2]=1

            2), j=3 ,求 next[3],

                            k = next[j-1]=next[3-1]=next[2]=1,

                            S[k]=S[1]=a   S[j-1]=S[3-1]=S[2]=b  S[k]!=S[j-1]    k=next[k]=next[1]=0 

                            next[3]=1

            3),j=4, 求next[4]

                            k=next[j-1]=next[4-1]=next[3]=1

                            S[k]=S[1]=a   S[j-1]=S[4-1]=S[3]=a   S[k]=S[j-1]   next[j]=k+1

                            next[4]=1+1=2

            4),j=5,求next[5]

                            k=next[5-1]=next[4]=2

                            S[k]=S[2]=b   S[j-1]=S[4]=b  S[k]=S[j-1]   next[j]=k+1

                            next[5]=2+1=3

            5),j=6,求next[6]

                            k=next[6-1]=next[5]=3

                            S[k]=S[3]=a   S[j-1]=S[5]=a    S[k]=S[j-1]   

                            next[j]=k+1=4

            6),j=7,求next[7]

                            k=next[7-1]=next[6]=4

                            S[k]=S[4]=b  S[j-1]=S[6]=a      S[k]!=S[j-1]    k=next[k]=next[4]=2

                            S[k]=S[2]=b   S[k]!=S[j-1]    k=next[k]=next[2]=1

                            S[k]=S[1]=a    S[k]=S[j-1]   

                            next[j]=k+1=2

            7),j=8,求next[8]

                            k=next[8-1]=next[7]=2

                            S[k]=S[2]=b   S[j-1]=S[7]=a     S[k]!=S[j-1]    k=next[k]=next[2]=1

                            S[k]=S[1]=a  S[k]=S[j-1]   

                            next[j]=k+1=2

            8),j=9,求next[9]

                            k=next[9-1]=next[8]=2

                            S[k]=S[2]=b   S[j-1]=S[8]=b   S[k]=S[j-1]   

                            next[j]=k+1=3

            9),j=10,求next[10]

                            k=next[10-1]=next[9]=3

                            S[k]=S[3]=a  S[j-1]=S[9]=a   S[k]=S[j-1]   

                            next[j]=k+1=4

            10),j=11,求next[11]

                            k=next[11-1]=next[10]=4

                            S[k]=S[4]=b  S[j-1]=S[10]=b  S[k]=S[j-1]   

                            next[j]=k+1=5

            11),j=12,求next[12]

                            k=next[12-1]=next[11]=5

                            S[k]=S[5]=a  S[j-1]=S[11]=a  S[k]=S[j-1]   

                            next[j]=k+1=6

    因此表格填写如下:

    j123456789101112
    S[j]ababaaababaa
    next[j]011234223456

    展开全文
  • KMP算法Next数组计算

    万次阅读 多人点赞 2012-10-31 21:18:29
    KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列(其实是)。先看看题吧。 (2011年下半年上午题) (2012年上半年上午题) 其实做这个题很简单,我先说说这个题里的各种概念。...

    KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列(其实是)。先看看题吧。

    (2011年下半年上午题)
    (2012年上半年上午题)
     
    其实做这个题很简单,我先说说这个题里的各种概念。
    给定的字符串叫做模式串T。j表示next函数的参数,其值是从1到n。而k则表示一种情况下的next函数值。p表示其中的某个字符,下标从1开始。看等式左右对应的字符是否相等。
    好了,开始做题了。
    首先,要把字符串填入到一个表格中:(拿第一个题为例)
     
     
    将j导入next函数,即可求得,
     
    j=1时, next[0]=0
     
    j=2时,k的取值为(1,j)的开区间,所以整数k是不存在的,那就是第三种情况, next[2]=1
     
    j=3时,k的取值为(1,3)的开区间,k从最大的开始取值,然后带入含p的式子中验证等式是否成立,不成立k取第二大的值。现在是k=2,将k导入p的式子中得,p1=p2,即“a”=“b”,显然不成立,舍去。k再取值就超出范围了,所以next[3]不属于第二种情况,那就是第三种了,即 next[3]=1
     
    j=4时,k的取值为(1,4)的开区间,先取k=3,将k导入p的式子中得,p1p2=p2p3,不成立。 再取k=2,得p1=p3,成立。所以 next[4]=2
     
    j=5时,k的取值为(1,5)的开区间,先取k=4,将k导入p的式子中得,p1p2p3=p2p3p4,不成立。 再取k=3,得p1p2=p3p4,不成立。 再取k=2,得p1=p4,成立。所以 next[4]=2
     
    j=6时,k的取值为(1,6)的开区间,先取k=5,将k导入p的式子中得,p1p2p3p4=p2p3p4p5,不成立。 取k=4,得p1p2p3=p3p4p5,不成立。再取k=3,将k导入p的式子中得,p1p2=p4p5,成立。所以 next[4]=3
     
    j=7时,k的取值为(1,7)的开区间,先取k=6,将k导入p的式子中得,p1p2p3p4p5=p2p3p4p5p6,不成立。  再取k=5,得 p1p2p3p4=p3p4p5p6 ,不成立。 再取k=4,得 p1p2p3=p4p5p6 ,成立。所以 next[4]=4
     
    j=8时,k的取值为(1,8)的开区间, 先取k=7,将k导入p的式子中得,p1p2p3p4p5p6=p2p3p4p5p6p7,不成立。  再取k=6,得p1p2p3p4p5=p3p4p5p6p7,不成立。 再取k=5,得p1p2p3p4=p4p5p6p7,不成立。 再取k=4,得p1p2p3=p5p6p7,不成立。 再取k=3,得p1p2=p6p7,不成立。再取k=2,得p1=p7,不成立。k再取值就超出范围了,所以next[3]不属于第二种情况,那就是第三种了,即 next[3]=1
     
    所以结果为:
     
    好了,第二题留给大家做吧。
     
    这篇博文就是讲了一下做题的过程,并没有讲到KMP算法的实质性的知识。不过next函数在KMP算法中至关重要。如果没有next函数,那么KMP算法就什么也不是了。下一篇博文会详细讲解KMP算法。敬请大家关注。
     

    看到别人有讲解KMP,大家也可以理解理解,更简单:https://blog.csdn.net/nanami809/article/details/49367159

     

     

    展开全文
  • KMP算法由两部分组成:第一部分,计算模式串的next或nextval数组。第二部分,利用计算好的模式串的nextval数组,进行模式匹配。 KMP算法中有next数组和nextval数组之分。 他们代表的意义和作用完全一样,完全可以.....
  • KMP算法next数组的手工计算方法

    千次阅读 2018-09-02 00:08:06
    KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体...
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • KMP算法next数组计算方法

    千次阅读 2019-11-18 13:09:02
    KMP算法中的next数组计算 是最近这几年在软件设计师考试中出现的,是一个比较热门的考点,也是容易出错的地方,下面我就简单的举一个例子,进一步讲解next数组的计算方法。 其实做这种题没什么难的,只要细心...
  • 关于KMP算法next数组的计算方法研究
  • KMP算法next数组的计算

    2017-08-12 17:15:35
    next数组的计算是kmp的核心,计算方法如下图所示
  • KMP算法next数组计算--字符串方式

    千次阅读 2017-06-19 23:51:17
    用字符串的方式说明模式串匹配中KMP算法求解next数组的方式
  • 昨天上课听老师讲KMP算法,倒在了next数组上,阅读了许多博客,希望能总结出next数组的计算算法。 个人见解可能比较粗劣。 推荐大佬的博客 next数组 先上代码 private int[] get_next(String needle){ int[] res = ...
  • 【算法分析】 KMP算法把专注点放在了“已匹配的前缀”。KMP算法的核心,是一个next数组。 在KMP算法的众多实现中,有许多种...但这两种定义方式,不影响它们有一致的计算方法,即“若第j-1位的字符与第x位的字符相等
  • KMP算法计算next值和nextval的值

    千次阅读 多人点赞 2019-12-27 18:22:50
    这里我就不介绍关于字符串匹配中KMP的优点,也不强调next的修正值比next的值好在哪,我们就说方法就行了。 一、next求解。 来,首先给我们一个序列 j 1 2 3 4 5 6 7 8 模式串 a ...
  • KMP算法以及next函数值、nextval函数值的计算方法

    千次阅读 多人点赞 2020-06-06 22:36:52
    KMP算法以及next函数值、nextval函数值的计算方法 数据结构中串涉及的内容即串的模式匹配,比较难理解的KMP算法,难在next函数值和nextval函数值的求解 一、问题描述 给定一个主串S及一个模式串P,判断模式串是否为...
  • 其他的部分看其他的博客就好啦,主要讲计算next数组时的思想。 主要对http://www.cnblogs.com/c-cloud/p/3224788.html。void makeNext(const char P[],int next[]) { int q,k;//q:模版字符串下标;k:最大前后缀...
  • KMP算法next数组的计算

    千次阅读 2018-06-09 20:52:07
    KMP算法next数组的计算
  • KMP算法next数组和nextval数组的快速简便计算方法总结
  • 笔试题目中经常要求计算KMP算法next数组,网上有很多讨论的文章,但是感觉都讲的不太清楚,特别是在如何手工计算这一方面,所以今天特别整理了一下放到这里,一来备忘,二来也希望给有缘人带来一些方便。...
  • KMP算法简介(next数组的计算方法

    千次阅读 2017-04-03 12:24:44
    下面附上一个next计算的算法不错的博客,我就是从这里面学到的next算法 http://www.cnblogs.com/yjiyjige/p/3263858.html 这篇博客使用java编写的KMP算法,我使用的是C语言,对于初学者应该比较好
  • 一、说明 (1)看到网上同一个字符串求 next 数组的值有两种,一种是 -1 ...算法都是一样的.KMP 的原始论文 (K,M,P 三个家伙写的原文)中是以 0 开头的,所以下面的写法是以 0 开头的. (2)关于 next 数组...
  • KMP 算法以及 next 数组计算

    千次阅读 2018-08-23 17:01:26
    看本文的同志们需要注意的是,本文没有按照一般的套路来介绍KMP算法,而是侧重于介绍KMP算法为什么这样做,关于KMP算法next非常值得一看的博客推荐如下: https://www.cnblogs.com/tangzhengyue/p/4315393.html ...
  • 哈哈哈KMP算法Next算法之如何计算简的描述抛出疑问所以看懂下面的图最简单的实现 KMP算法Next算法之如何计算 简的描述 K,J为两个“指针”,K指向前缀,J指向后缀。 当P[K]==P[J],则 K++,J++,匹配下一个...
  • KMPnext数据的计算方法的重点一直get不到,现在终于看懂了,趁热打铁把理解的过程记录下来。 next数组指的是字符串的最大的公共前后缀字符子串的长度。它的计算其实是一个动态规划的过程,将前面已经计算过的结果...
  • 此篇文章总结的 基于kmp中的模式串方式 关于next图解如下 举例:字符串 “ababaa” 索引 0 1 2 3 4 5 字符 a b a b a a next 0 0 1 1 2 3 ...
  • 手算KMP算法next数组

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,256
精华内容 2,502
关键字:

kmp算法next计算方法