精华内容
下载资源
问答
  • KMP算法详解

    万次阅读 多人点赞 2019-04-25 22:05:03
    KMP算法是一种字符串模式匹配算法,不同的来源讲解方式也不一样,很容易混乱,在这里以一种特殊的方式来讲解KMP算法,希望大家不再被这个问题所困扰。 一. 一些基础问题 什么是字符串的模式匹配? 给定两个串S=...

    首先感谢大佬博主v_JULY_v(v_JULY_v)在从头到尾彻底理解KMP(2014年8月22日版)一文中给我在写博客组织语言上的启发,以及部分图片的转载。

    KMP算法是一种字符串模式匹配算法,不同的来源讲解方式也不一样,很容易混乱,在这里以一种特殊的方式来讲解KMP算法,希望大家不再被这个问题所困扰。

    一. 一些基础问题

    1. 什么是字符串的模式匹配?
      给定两个串S=“s1s2s3 …sn”和T=“t1t2t3 …tn”,在主串S中寻找子串T的过程叫做模式匹配,T称为模式。
    2. 如何寻找?
      我们先从比较好理解的暴力匹配(朴素模式匹配BF算法)开始,进而引出KMP算法。

    二. 暴力匹配(朴素模式匹配BF)

    规定i是主串S的下标,j是模式T的下标。现在假设现在主串S匹配到 i 位置,模式串T匹配到 j 位置。

    • 如果当前字符匹配成功(即S[i] = T[j]),则i++,j++,继续匹配下一个字符;
    • 如果失配(即S[i] != T[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯到本次失配起始字符的下一个字符,j 回溯到0。
    int BF(char S[],char T[])
    {
    	int i=0,j=0;
    	while(S[i]!='\0'&&T[j]!='\0')
    	{
    		if(S[i]==T[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(T[j]=='\0') return (i-j);     //主串中存在该模式返回下标号 
    	else return -1;     //主串中不存在该模式 
    }
    

    我们用一个例子来说明一些这个算法:现在有主串S:ababcabcacbab,模式串T:abcac。我们来看一下是如何匹配的。i从0开始,j也从0开始。

    在第一次匹配中,i从0开始,j从0开始。当i=2,j=2时匹配失败,此时i回溯到1,j回溯到0。
    在这里插入图片描述
    第二次匹配中,i从1开始,j从0开始。当i=1,j=0时匹配失败,此时i回溯到2,j回溯到0。
    在这里插入图片描述
    第三次匹配中,i从2开始,j从0开始。当i=6,j=4时匹配失败,此时i回溯到3,j回溯到0。
    在这里插入图片描述
    第四次匹配中,i从3开始,j从0开始。当i=3,j=0时匹配失败,此时i回溯到4,j回溯到0。
    在这里插入图片描述
    第五次匹配中,i从4开始,j从0开始。当i=4,j=0时匹配失败,此时i回溯到5,j回溯到0。
    在这里插入图片描述
    第六次匹配中,i从5开始,j从0开始。i=10,j=5,T中全部字符比较完,匹配成功,返回本次匹配起始位置下标i - j。(i=9和j=4的时候匹配成功,i和j会再加一次,所以i=10,j=5)
    在这里插入图片描述
    可见,如果i已经匹配了一段字符后出现了失配的情况,i会重新往回回溯,j又从0开始比较。这样浪费的大量的时间。在第三次匹配结束后,我们可以发现:i=3和j=0,i=4和j=0以及i=5和j=0是不必进行的,因为从第三次部分匹配过程中我们可以得出,主串中第3,4,5个字符必然是‘b’,‘c’,‘a’(即与模式串的第1,2,3个字符分别对应相等),而模式的首字符是‘a’,它分别与‘b’,‘c’不等,与‘a’相等。如果将模式向右滑动3个字符继续进行i=6和j=1时的字符比较,很明显会加快进程。这样就引出了我们的KMP算法,不回溯i,加快匹配效率。

    三. KMP算法

    1. 背景
    KMP算法一种改进的模式匹配算法,是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表,KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于:每当从某个起始位置开始一趟比较后,在匹配过程中出现失配,不回溯i,而是利用已经得到的部分匹配结果,将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后,继续按规则进行下一次的比较。
    2. 算法流程 (这部分读完可能会有很多问题,没关系,我们会针对每一步进行详细的讲解)
    规定i是主串S的下标,j是模式T的下标。现在假设现在主串S匹配到 i 位置,模式串T匹配到 j 位置。

    • 如果j = -1,则i++,j++,继续匹配下一个字符;
    • 如果S[i] = T[j],则i++,j++,继续匹配下一个字符;
    • 如果j != -1,且S[i] != P[j],则 i 不变,j = next[j]。此举意味着失配时,接下来模式串T要相对于主串S向右移动j - next [j] 位。
    int KMP(int start,char S[],char T[])
    {
    	int i=start,j=0;
    	while(S[i]!='\0'&&T[j]!='\0')
    	{
    		if(j==-1||S[i]==T[j])
    		{
    			i++;         //继续对下一个字符比较 
    			j++;         //模式串向右滑动 
    		}
    		else j=next[j];
    	}
    	if(T[j]=='\0') return (i-j);    //匹配成功返回下标 
    	else return -1;                 //匹配失败返回-1 
    }
    

    到这里,我们一点点来引出问题,我们来一一解答(后面的问题引出可能还会引出另一个问题,为方便读者阅读,问题标注成蓝色,对应问题解决的地方标注成红色):

    (1)next是什么???它是怎么来的???

    首先我们来解释一个名词:最长公共前后缀。假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj,我们就说在P串中有一个最大长度为k+1的公共前后缀。

    (2)如何寻找前后缀???

    • 找前缀时,要找除了最后一个字符的所有子串。
    • 找后缀时,要找除了第一个字符的所有子串。

    问题(2)已解决

    现在有串P=abaabca,各个子串的最大公共前后缀长度如下表所示:
    在这里插入图片描述
    这样,公共前后缀最长长度就会和串P的每个字符产生一种对应关系:
    在这里插入图片描述
    这个表的含义是在当前字符作为最后一个字符时,当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时,当前子串abaabc并没有公共前后缀。
    接下来我们就用这个表来引出next数组,next 数组的值是除当前字符外(注意不包括当前字符)的公共前后缀最长长度,相当于把上表做一个变形,将表中公共前后缀最长长度全部右移一位,第一个值赋为-1。例如c对应next值的意义是,c之前(不包括c)的子串abaab所拥有的公共前后缀最长长度为2,我们称next数组中的值为失效函数值,也就是c的失效函数值为2。(当然这是我们手动推得,我们后续会用编程思想来推得next数组)
    在这里插入图片描述
    我们手动推得了next数组,那就来体验一下KMP算法的流程:现在有主串S:ababcabcacbab,模式串T:abcac。i从0开始,j也从0开始。
    根据上述方法可以知道,T的中每个字符对应的失效函数值为:
    在这里插入图片描述
    第一次匹配中,i从0开始,j从0开始。当i=2,j=2时匹配失败,此时i不动,next[j]=next[2]=0,接下来模式串T要相对于主串S向右移动j - next [j] = 2 位,j回溯到0。
    在这里插入图片描述
    第二次匹配中,i从2开始,j从0开始。当i=6,j=4时匹配失败,此时i不动,next[j]=next[4]=1,接下来模式串T要相对于主串S向右移动j - next [j] = 3位,j回溯到1。
    在这里插入图片描述
    第三次匹配中,i从6开始,j从1开始。当i=10,j=5时匹配成功,返回i - j = 5。
    在这里插入图片描述
    我们根据next数组进行匹配,不失一般性的话,我们做如下总结:
    当主串S与模式串P失配时,j=next[j],P向右移动j - next[j]。也就是当模式串P后缀pj-kpj-k+1…pj-1与主串S的si-ksi-k+1…si-1匹配成功,但是pj和si失配时,因为next[j]=k,相当于在不包含pj的模式串中有最大长度为k的相同前后缀,也就是p0p1…pk-1 = pj-kpj-k+1…pj-1,所以令j = next[j],让模式串右移j - next[j]位,使模式串p0p1…pk-1 与主串si-ksi-k+1…si-1对齐,让pk和si继续匹配。如下图所示:
    在这里插入图片描述
    KMP的next数组告诉我们:当模式串中的某个字符跟主串中的某个字符失配时,模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟主串在i 处的字符匹配失配时,下一步用next [j] 处的字符继续跟主串i 处的字符匹配,相当于模式串向右移动 j - next[j] 位。

    问题(1)已解决

    好了,至此我们把next原理全部讲完,但是我们不能只停留在手动推导的层面上,我们再从编程下手继续理解next数组,最后再推出KMP算法。

    3. 递推求next数组

    我们很容易的可以知道,next[0] = -1。next[1] = 0也是容易推得的。那么(3)当j>1时,如果我们已知了next[j],那么next[j+1]怎么求得呢???

    假定我们给定了某模式串,且已知next[j] = k,现在求得next[j+1]等于多少。

    我们分两种情况分析:

    1. 当pk=pj时,next[j + 1] = next[j] + 1 = k + 1,代表字符E前的模式串中,有长度k+1 的最大公共前后缀。
      在这里插入图片描述
    2. 当pk ! = pj时,说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj,这时ABC与ABD不相同,也就是字符E前的模式串中没有长度为k+1的最大公共前后缀,所以next[j + 1] = next[j] + 1不再适用,我们只能寻找更短的最大公共前后缀。
      在这里插入图片描述
      这样看来,如果我们能在p0p1…pk-1pk中不断递归索引k = next[k],找到一个字符pk’,也是D的话,那么最大公共前后缀长度就为k’+1。此时pk’=pj,且p0p1…pk’-1pk’ = pj-k’pj-k’+1…pj-1pj。从而next[j+1] = k’ + 1 = next[k’] + 1。否则前缀没有D,next[j+1] = 0。

    问题(3)已解决

    (4)为什么递归前缀索引k = next[k],就能找到长度更短的相同前缀后缀呢???我们用这张图来分析:
    在这里插入图片描述
    在pk != pj时,k = next[k],用pnext[k]去跟pj继续匹配。为什么不用其他值和pj匹配呢?我们可以看到,在pj之前,有一段长度为k的已匹配串;在pk之前有一段蓝色的已匹配串,说明pk字符前有一段长度为next[k]的最大公共前后缀(蓝色的那段)。如果pk != pj,说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj,那么我们只能找更短的最大公共前后缀,此时因为pk和pnext[k]前面的蓝色串已完全匹配,如果pnext[k]能和pj匹配 ,那么我们便找到了我们需要的串。如果还是不匹配,下一步pnext[next[k]…]去跟pj继续匹配,直到找到长度更短公共前后缀。
    问题(4)已解决
    综上,我们可以写出求next数组的递推代码:

    void GetNext(char T[])
    {
    	int j=0,k=-1;
    	next[j]=k;
    	while(T[j]!='\0')
    	{
    		if(k==-1||T[j]==T[k])
    		{
    			j++;
    			k++;
    			next[j]=k;
    		}
    		else k=next[k];
    	}
    }
    

    其实,我们在分析的过程中可以发现,k=next[next[k]…]这一步其实非常的类似于递归。因此我们也给出递归的代码供读者参考。

    int GetNext(int j,char T[])
    {
    	if(j==0)return -1;
    	if(j>0)
    	{
    		int k=GetNext(j-1,T);
    		while(k>=0)
    		{
    			if(T[j-1]==T[k])return k+1;
    			else k=GetNext(k,T);
    		}
    		return 0;
    	}
    	return 0;
    }
    
    展开全文
  • KMP算法详解KMP算法详解KMP算法详解KMP算法详解
  • KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
  • kmp算法详解

    多人点赞 热门讨论 2021-08-31 16:54:58
    对于kmp的鼎鼎大名,不只是博主自己,想必还有更多小伙子们听说过,也相信都去了解过,博主亦是这样,但是真正去理解这个过程,确是异常的折磨人,在kmp算法里面捣鼓了整整3天,博主终于找到了用更好理解的话语进行解释了,便...

    前言

    对于kmp的鼎鼎大名,不只是博主自己,想必还有更多小伙子们听说过,也相信都去了解过,博主亦是这样,但是真正去理解这个过程,确是异常的折磨人,在kmp算法里面捣鼓了整整3天,博主终于找到了用更好理解的话语进行解释了,便迫不及待的进行分享.


    例题引入


    假如有一个文本串T,内容为cadefgdefghp,有一个模式串P,其内容为defgh,请问P是否在T内?如果在,请返回P在T中的索引位置,如果不在,请返回-1.


    简单算法BF

    对于此题,我想大部分人都有一个简单思路,那就是T和P一一匹配,当匹配一个字符后,就挨个匹配后面;如果在中间部分不匹配,那么T讲回到最开始匹配字符的下一个字符处,P回到索引为0处.如下图:

    动画

    而这种算法我们称为朴素算法(BF),代码博主会贴在下面:

    int BF(char T[], char P[])
    {
        int i = 0, j = 0;
        while (i < strlen(T) && j < strlen(P))
        {
            if (T[i] == P[j])  //如果相等,就继续从这往后匹配
            {
                i++, j++;
            }
            else
            {
                i = i - j + 1;     //如果不等,i就返回最开始匹配位置下一个位置(见上图)
                j = 0;             //p返回到索引为0重新开始
            }
        }
        if (j >= strlen(P))   //当匹配成功时,j一定移动到P字符串末尾,所以j必须有此条件
            return i - j;
        else 
            return -1;
    }
    

    经典算法KMP

    为什么有KMP,他的目的就是解决我们重复匹配的问题,比如下图:

    image-20210823155233574

    我们发现g和e不匹配了,按照BF算法,文本串(上方字符串)位置会回到b位置,模式串(下方)会重新回到索引为0处然后继续比对.

    image-20210823155647071

    而如果我们按照人的思维会怎样继续对比呢?没错,我们并不会像BF那样笨,如果是人,会直接让文本串不动,直接让模式串开始重新匹配:

    image-20210823160011513

    也就是文本串此时索引不动,而模式串索引回到了0,并从此处开始继续匹配.记住这句话!!!


    我们再举一个例子,假设在文本串efabcabpabcabe中匹配abcabe,如下图:

    image-20210823160634394

    我们先是一个一个的匹配,但是当匹配到p和e时,发现不匹配了,按照BF算法,文本串会回到索引为3位置,模式串会回到索引为0位置.

    image-20210823161300023

    但是如果是人呢?会怎样做?我们会让模式串索引0位置和文本串索引5位置对齐,因为对齐后都有ab,所以模式串就从索引为2位置继续进行匹配.

    image-20210823161424049

    也就是文本串此时不动,而模式串索引回到2,并从此开始继续匹配.记住这句话!!!


    我们最后再举一个例子:假设有文本串efabcdabcabcabe,模式串abcdabc,然后开始正常匹配

    image-20210823161704440

    在这里,我们发生了失配,如果按照BF算法,我们会让文本串回到索引为3位置处,而模式串回到索引0处:

    image-20210823162122640

    但是如果是人类呢? 会怎样做? 没错,我们会让模式串与文本串的索引6位置处对齐,而文本串不动.然后发现对齐以后,文本串和模式串都有abc,所以我们不管abc,而是让模式串从索引为3处开始和文本串对比:

    image-20210823162441496

    也就是文本串此时不动,而模式串索引回到3,并从此开始继续匹配.记住这句话!!!


    大家分别纵观上面三个例子,我们都做了什么相同操作?

    • 当失配时:
      • 文本串位置不动
      • 模式串的索引直接从某个位置开始继续和文本串适配位置进行匹配

    我们再来看看规律,

    第一个例子: 文本串此时不动,而模式串索引回到0,并从此开始继续匹配.

    • 原因:模式串失配位置前面有0个重复的元素

    第二个例子:文本串此时不动,而模式串索引回到2,并从此开始继续匹配.

    • 原因: 模式串失配位置前面有2个重复的元素,即ab

    第三个例子:文本串此时不动,而模式串索引回到3,并从此开始继续匹配.

    • 原因: 模式串失配位置前面有3个重复的元素,即abc

    也就是说!!!,当在中途匹配过程中发生失败,我可以不再让文本串回走很长一段举例,而是让模式串进行继续匹配,至于模式串下一步应该会到哪个位置,取决于匹配失败字符前的相同前后缀字符(后面会介绍前后缀)长度


    我们再试试一个例子,看看是这个规律吗?比如文本串efacadmp,模式串acabef

    image-20210823165420095

    此时失配了,模式串失配字符b前面有1个重复的元素a,所以模式串直接从索引为1开始进行继续匹配,看看是否对:

    image-20210823165604273

    完全没问题,因为在模式索引0前有一个字符a,而文本串对应位置也有一个字符a,所以模式串直接从索引为1开始匹配

    也就是说一旦发生失配,人类执行时,会按照如下步骤:

    • 不动文本串
    • 模式串位置直接回到索引为k处(k是失配位置前面所有字符串中最大重复元素数量)

    而这些步骤用代码写出来就是kmp

    即kmp算法不像BF算法那样,避免了文本串的索引返回,而是直接定位模式串下一个匹配位置.


    kmp理解难点1

    我们已经清楚了kmp的算法步骤,而难点1就在于求k

    而k就是 字符串的最大相同前后缀长度

    **前后缀概念: **

    • 前缀: 字符串中除了最后一个字符外的所有顺序集合

      • 比如有字符串abcdef,那么他的前缀有a,ab,abc,abcd,abcde
    • 后缀:字符串中除了第一个字符外的所有顺序集合

      • 比如有字符串abcdef,那么他的后缀有f,ef,def,cdef,bcdef
    • 最大相同前后缀: 前缀集合和后缀集合的交集中最大长度者

      • 比如有字符串ababab,他的前后缀交集有ab,abab,所以最长相同前后缀就是abab

    kmp理解难点2

    我们知道,当模式串与主串不匹配时,而主串不动,模式串的索引跳到k处,k值是b当前不匹配字符前的所有字符中最大相同前后缀长度

    所以我们为了方便处理,便用一个数组进行储存一段字符串的最大前后缀最长度

    假设有字符串ababaaaba,则:

    字符串ababaaaba
    索引012345678
    k值001231121

    解释:

    • 在索引为3下,k值是2,代表着[0,3]中的字符串中相同前后缀的最大长度为2

    • 在索引为6下,k值是1,代表着[0,6]中的字符串中相同前后缀的最大长度为1

    • 在索引为0下,k值0,代表着[0,0]中的字符串,即一个字符是没有前后缀的,最大长度为0


    我们给储存k值的数组起名叫做next.这也就是我们kmp算法中的精华所在


    kmp最难理解点3

    博主在学习kmp算法中时候,发现很多文章与视频都是只给了手动算next数组方法,对于代码部分便是一笔跳过,而这才是KMP中最最最难理解的一部分代码,下面博主用自己的理解给大家分享下自己的拙见

    我们还是像介绍kmp算法一样,我们还是先用自己的第一思路来处理,然后写代码,最后进阶精华kmp数组求法:

    • 我们的第一思路是什么? 没错,那就是前缀和后缀一对一对的比较,比如有下面一段字符串str:

    abbabba

    我们用变量i进行指示比的是第几对,从1开始.

    我们用变量count进行计数,当出现一对相同前后缀,则count = i,最后count值就是最大长度

    • 当i = 1时候,第一对前缀是"a",后缀是"a",后缀的位置是strlen(str)-1,前后缀相同,count等于1
    • 当i = 2时候,第一对前缀是"ab",后缀是"ba",后缀的位置是strlen(str)-2,前后缀不同,count不管
    • 当i = 4时候,第一对前缀是"abba",后缀是"abba",后缀的位置是strlen(str)-4,前后缀相同,count等于4

    所以大概代码如下:

    int count = 0;
    for(int i = 1;i < strlen(str);i++)               //i不能等于strlen(str),因为前后缀分别不包含尾字符和首字符
    {
        if(strncmp(str,str+strlen(str)-i,i) == 0)    //如果第几对前后缀相同,则count等于几
        {                                            //str+strlen(str)-i 是指针加减整数的意义
            count = i;
        }
    }
    

    而我们是需要求一个数组,所以我们就把字符串拆成更多个小字符串,然后又分别求每个小字符串的最大前后缀长度,思路和上面一样

    void next(char str[],int next[])
    {
        int i = 1,j = 1,count = 0;
        //i代表第几对,j代表索引[0,j]的字符串,count代表最大长度   
        
        next[0] = 0; //首字符一定为0,因为之后一个字符,没有前后缀
        
        for(j = 1;j<strlen(str);j++)
        {
            count = 0;
            for(int i = 1;i < strlen(str);i++)               //i不能等于strlen(str),因为前后缀分别不包含尾字符和首字符
            {
                if(strncmp(str,str+strlen(str)-i,i) == 0)    //如果第几对前后缀相同,则count等于几
                {                                            //str+strlen(str)-i 是指针加减整数的意义
                    count = i;
                }
            }
            next[j] = count;
        }
    }
    

    我们已经成功的用自己的方法求出来了next数组,但是大家有没有发现这样求解有一个很大的缺陷?

    • 那就是我们每次在求解[0,j]中的字符串最大相同前后缀时,我们都是从第一对的一个字符,到第j对的j个字符进行对比.

    • 而在求解[0,j+1]中的字符串最大相同前后缀时,我们又要从第一对的第一个字符,到第j+1对的j+1个字符进行对比.

    在比较的过程中我们比较了很多不相同前后缀的字符串,那么我们想一想,可不可以换一种思路,不再像上面那样每次都要从一个字符开始进行匹配,避免多次匹配不相同前后缀字符串? 答案是完全可以!!!

    下面,请大家一定记住这句话,不要觉得这些话很简单,后面正是这些话才能明白某些代码:

    相同前后缀 == 相同前缀 == 相同后缀 !!!— --- — --- — --- — --- — --- — --- — --- — --- — --- — --- — --- ---- — --- — ---标号①

    如果一段字符串存在相同前后缀,那么相同前缀一定可以在后缀(注意,没有相同两字)中找到,并且相同前缀一定是最长后缀末尾,相同前缀的长度一定小于等于最长后缀长度— --- — --- — --- — --- — --- — --- — --- — --- — --- — --- — --- —标号②

    举个例子:

    有一段字符串ababa.

    • 相同前后缀有aaba,而后缀有a,ba,aba,baba,这就是这句话— --- —相同前缀一定可以在后缀中找到的意思
    • 该段字符串最长后缀为baba,相同前缀为a,是最长后缀的末尾,相同前缀为aba,是最长后缀的末尾.
      • 所以说— --- — 相同前缀一定是最长后缀末尾
    • 相同前缀的长度分别是1和3都小于最长后缀的长度4

    既然我们目的是为了减少不必要的不同前后缀字符串比对,那么我们的方法是什么呢?

    答曰: 给最长相同前缀新增一个字符,然后判断是否在最长后缀中.(请看标号①语句)

    • 如果不在,我们就判断原最长相同前缀是否在最长后缀中…

    • 如果在,说明此时的字符串中最长相同前后缀长度是原最长相同前后缀长度加1(步骤重复上面)

    我们现在要开始清楚一些概念了:

    1. 我们用j表示一段字符串([0,j]的字符串)最长后缀的尾巴的索引,j的初始值设为1

    2. 用k表示字符串中最长相同前缀的长度(这句话本身还表达了另一个意思,是最长相同前缀尾巴后一个索引,这个很重要),k初始为0

      • 比如有字符串ababa,假设此时k等于3,说明此时最长相同前后值长度是3,而索引为3字符却是最长相同前缀尾末,
    3. next数组存储的是最长相同前后缀字符长度,则next[j]表示索引在[0,j]的字符串中最长相同前后缀的长度

    所以他们一定有下图关系:

    image-20210824102151162


    现在大家再看看上面我们说的新的比较方法的步骤,然后下面的代码结合上面这张图分析


    (下面这些话大家一定要静下心来想,博主会贴图再详细解释)

    如果不存在,怎么判断?

    • 答曰:

    • while(k>0 && p[k] != p[j])  //k为什么大于0,后面会解释
      {
          k = next[k-1];         //说明给原最长相同前缀加一个字符后,判断出不等,即[0,k]的字符串不在后缀中
      }
      
      其实k = next[k-1]大家可能还是不理解,但是大家想想我们的目的,避免比较不相同前后缀,而next数组装的就只有相同前后缀长度.
      既然[0,k]字符串的最长前缀不在后缀中,我们就需要比较[0,k-1]中的最长前缀是否在后缀.
          而next[k-1]的意义不就是[0,k-1]中最长相同前后缀字符串长度吗?
      

    给最长相同前缀新增一个字符,如何判断在最长后缀中?

    • **答曰: **

    • if(p[k] == p[j])    //因为p[0,k-1]等于p[j-k,j-1],而p[0,k-1]就是目前为止最长相同前缀,所以只需要判断p[k]和p[j]了
      {
          next[j] = k+1; //如果相等,[0,j]中的最长相同前后缀长度等于原最长前后缀长度加一.
          k++;           //更新现在的最长相同前后缀长度
      }
      else               //else就是处理当k等于0,且p[k]不等于p[j]时候,说明next[j]应该为0
      {
          next[j] = 0;
      }
      

    所以最后求next数组的代码就是

    void get_next(char p[100],int next[100]) 
    {
    
        next[0] = 0;
        int j = 1;
        int k = 0;
        //如果有效前缀增加一个值和新增后缀不等,
        for(j = 1; j < strlen(p); j++)
        {
            while (k>0 && p[k] != p[j])
            {
                k = next[k - 1];   
            }
            if (p[k] == p[j])
            {
                next[j] = ++k;
            }
            else   //这一步是索引为1时候,k等于0,且不等的条件
            {
                next[j] = 0;
            }
        }
    }
    

    kmp代码

    int kmp(char s[100],char p[100])
    {
        int i = 0, j = 0;
        int next[100];
        get_next(p,next);
        while (i < strlen(s) && j < strlen(p))
        {
            if (s[i] == p[j])
            {
                i++, j++;
            }
            else if (j > 0)
            {
                j = next[j - 1];
            }
            else
            {
                i++;
            }
        }
    
        if (j >= strlen(p)) return i - j;
        else
            return -1;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,614
精华内容 1,845
关键字:

kmp算法详解