精华内容
下载资源
问答
  • KMP算法流程图

    2021-09-15 00:34:20
  • 数据结构KMP算法详解(超详细)

    万次阅读 多人点赞 2020-02-18 22:02:42
    前言 KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美...这篇文章将尽量以最简单的方式介绍KMP算法以及他的改进,文章的开始我先对kmp算法的三位创始人Knuth,Morris,Pratt致敬,懂得这...

    KMP算法配图详解

    前言

    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂,很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KMP算法的三位创始人Knuth,Morris,Pratt致敬,懂得这个算法的流程后你真的不得不佩服他们的聪明才智。

    KMP解决的问题类型

    KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。比如主串s=“goodgoogle”,子串t=“google”。现在我们要找到子串t 在主串s 中的位置。大家肯定觉得这还不简单,不就在第五个嘛,一眼就看出来了。
    当然,在字符串非常少时,“肉眼观察法”不失为一个好方法。但如果要你在一千行文本里找一个单词,我想一般人都会数得崩溃吧。这就让我想起来考试的时候,如果一两道选择题不会。这时候,“肉眼观察法”可能效果不错,但是如果好几道大题不会呢?“肉眼观察法”就丝毫不起效了。所以打铁还需自身硬,我们把这种枯燥的事以一定的算法交给计算机处理。
    第一种我们容易想到的就是暴力求解法。
    这种方法也叫朴素的模式匹配

    简单来说就是:从主串s 和子串t 的第一个字符开始,将两字符串的字符一一比对,如果出现某个字符不匹配,主串回溯到第二个字符,子串回溯到第一个字符再进行一一比对。如果出现某个字符不匹配,主串回溯到第三个字符,子串回溯到第一个字符再进行一一比对…一直到子串字符全部匹配成功。

    下面我们通过图片展示这个过程:
    竖直线表示相等,闪电线表示不等
    第一个过程:子串“goo”部分与主串相等,'g’不等,结束比对,进行回溯。
    在这里插入图片描述
    第二个过程:开始时就不匹配,直接回溯
    在这里插入图片描述
    第三个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第四个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第五个过程:匹配成功
    在这里插入图片描述
    大家可能会想:这个方法也太慢了吧!求一个子串位置需要太多的步骤。而且很多步骤根本不必要进行。
    这个想法非常好!!很多伟大的思想都是在一步步完善更正已有方法中诞生的。这种算法在最好情况下时间复杂度为O(n)。即子串的n个字符正好等于主串的前n个字符,而最坏的情况下时间复杂度为O(m*n)。相比而言这种算法空间复杂度为O(1),即不消耗空间而消耗时间。

    下面就开始进入我们的正题:KMP算法是怎样优化这些步骤的。其实KMP的主要思想是:“空间换时间”。
    大家打起精神,认真看下面的内容
    首先,为什么朴素的模式匹配这么慢呢?
    你再回头看一遍就会发现,哦,原来是回溯的步骤太多了。所以我们应该尽量减少回溯的次数。
    怎样做呢?比如上面第一个图:当字符’d’与’g’不匹配,我们保持主串的指向不变,
    主串依然指向’d’,而把子串进行回溯,让’d’与子串中’g’之前的字符再进行比对。
    如果字符匹配,则主串和子串字符同时右移。
    至于子串回溯到哪个字符,这个问题我们先放一放。

    我先提出一个概念:一个字符串最长相等前缀和后缀。
    教科书常用的手段是:在此处摆出一堆数学公式让大家自行理解。
    在这里插入图片描述
    这也是为什么看计算机学科的书没有较好的数学基础会很痛苦。(当初我为什么不好好学数学T_T)
    大家先不要强行理解数学公式,且听我慢慢道来:
    我给大家个例子。
    字符串 abcdab
    前缀的集合:{a,ab,abc,abcd,abcda}
    后缀的集合:{b,ab,dab,cdab,bcdab}
    那么最长相等前后缀不就是ab嘛.

    做个小练习吧:
    字符串:abcabfabcab中最长相等前后缀是什么呢:
    对就是abcab
    好了我们现在会求一个字符串的前缀,后缀以及最长相等前后缀了。
    这个概念很重要。到这里如果都看懂了,可以鼓励一下自己,然后回想一遍,再往下看。
    之前留了一个问题,子串回溯到哪个字符,现在可以着手解决了。

    图解KMP

    现在我们先看一个图:第一个长条代表主串,第二个长条代表子串。红色部分代表两串中已匹配的部分,
    绿色和蓝色部分分别代表主串和子串中不匹配的字符。
    再具体一些:这个图代表主串"abcabeabcabcmn"和子串"abcabcmn"。
    在这里插入图片描述
    在这里插入图片描述
    现在发现了不匹配的地方,根据KMP的思想我们要将子串向后移动,现在解决要移动多少的问题。
    之前提到的最长相等前后缀的概念有用处了。因为红色部分也会有最长相等前后缀。如下图:
    在这里插入图片描述
    在这里插入图片描述
    灰色部分就是红色部分字符串的最长相等前后缀,我们子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐。
    在这里插入图片描述
    在这里插入图片描述
    这一步弄懂了,KMP算法的精髓就差不多掌握了。接下来的流程就是一个循环过程了。事实上,每一个字符前的字符串都有最长相等前后缀,而且最长相等前后缀的长度是我们移位的关键,所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
    所以next[i]=j,含义是:下标为i 的字符前的字符串最长相等前后缀的长度为j。
    我们可以算出,子串t= "abcabcmn"的next数组为next[0]=-1(前面没有字符串单独处理)
    next[1]=0;next[2]=0;next[3]=0;next[4]=1;next[5]=2;next[6]=3;next[7]=0;

    abcabcmn
    next[0]next[1]next[2]next[3]next[4]next[5]next[6]next[7]
    -10001230

    本例中的蓝色c处出现了不匹配(是s[5]!=t[5]),
    在这里插入图片描述
    我们把子串移动,也就是让s[5]与t[5]前面字符串的最长相等前缀后一个字符再比较,而该字符的位置就是t[?],很明显这里的?是2,就是不匹配的字符前的字符串 最长相等前后缀的长度。
    在这里插入图片描述
    也是不匹配的字符处的next数组next[5]应该保存的值,也是子串回溯后应该对应的字符的下标。 所以?=next[5]=2。接下来就是比对是s[5]和t[next[5]]的字符。这里也是最奇妙的地方,也是为什么KMP算法的代码可以那么简洁优雅的关键。
    我们可以总结一下,next数组作用有两个:
    一是之前提到的,

    next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

    二是:

    表示该处字符不匹配时应该回溯到的字符的下标

    next有这两个作用的源头是:之前提到的字符串的最长相等前后缀
    想一想是不是觉得这个算法好厉害,从而不得不由衷佩服KMP算法的创始人们。

    KMP算法的时间复杂度

    现在我们分析一下KMP算法的时间复杂度:
    KMP算法中多了一个求数组的过程,多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m),因后面匹配中主串不回溯,比较次数可记为n,所以KMP算法的总时间复杂度为O(m+n),空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n),KMP算法提速是非常大的,这一点点空间消耗换得极高的时间提速是非常有意义的,这种思想也是很重要的。
    下面还有更厉害的,我们一起来分析具体的代码。

    求next数组的代码

    下面我们一起来欣赏计算机如何求得next数组的

    typedef struct
    {	
    	char data[MaxSize];
    	int length;			//串长
    } SqString;
    //SqString 是串的数据结构
    //typedef重命名结构体变量,可以用SqString t定义一个结构体。
    void GetNext(SqString t,int next[])		//由模式串t求出next值
    {
    	int j,k;
    	j=0;k=-1;
    	next[0]=-1;//第一个字符前无字符串,给值-1
    	while (j<t.length-1) 
    	//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
    	//所以最后一次经过while循环时j为t.length-2
    	{	
    		if (k==-1 || t.data[j]==t.data[k]) 	//k为-1或比较的字符相等时
    		{	
    			j++;k++;
    			next[j]=k;
    			//对应字符匹配情况下,s与t指向同步后移
    			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
    			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
           	}
           	else
    		{
    			k=next[k];
    			**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
    			//也表示该处字符不匹配时应该回溯到的字符的下标
    			//这个值给k后又进行while循环判断,此时t.data[k]即指最长相等前缀后一个字符**
    			//为什么要回退此处进行比较,我们往下接着看。其实原理和上面介绍的KMP原理差不多
    			//printf("(2) k=%d\n",k);
    		}
    	}
    }
    

    解释next数组构造过程中的回溯问题

    大家来看下面的图:
    下面的长条代表子串,红色部分代表当前匹配上的最长相等前后缀,蓝色部分代表t.data[j]。
    在这里插入图片描述在这里插入图片描述

    KMP算法代码解释

    int KMPIndex(SqString s,SqString t)  //KMP算法
    {
    
    	int next[MaxSize],i=0,j=0;
    	GetNext(t,next);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{
    			i++;j++;  			//i,j各增1
    		}
    		else j=next[j]; 		//i不变,j后退,现在知道为什么这样让子串回退了吧
        }
        if (j>=t.length)
    		return(i-t.length);  	//返回匹配模式串的首字符下标
        else  
    		return(-1);        		//返回不匹配标志
    }
    

    KMP算法的改进

    为什么KMP算法这么强大了还需要改进呢?
    大家来看一个例子:
    主串s=“aaaaabaaaaac”
    子串t=“aaaaac”
    这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。'c’前的’a’回溯后的字符依然是‘a’。
    我们知道没有必要再将‘b’与‘a’比对了,因为回溯后的字符和原字符是相同的,原字符不匹配,回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为:nextval数组。KMP算法的改进可以简述为: 如果a位字符与它next值指向的b位字符相等,则该a位的nextval就指向b位的nextval值,如果不等,则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串"ababaaab"的next数组以及nextval数组分别为:

    下标01234567
    子串ababaaab
    next-10012311
    nextval-10-10-1310

    我们来分析下代码:

    void GetNextval(SqString t,int nextval[])  
    //由模式串t求出nextval值
    {
    	int j=0,k=-1;
    	nextval[0]=-1;
       	while (j<t.length) 
    	{
           	if (k==-1 || t.data[j]==t.data[k]) 
    		{	
    			j++;k++;
    			if (t.data[j]!=t.data[k]) 
    //这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
    //为什么?因为没有这处if判断的话,此处代码是next[j]=k;
    //next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
    				nextval[j]=k;
               	else  
    				nextval[j]=nextval[k];
    //这一个代码含义是不是呼之欲出了?
    //此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
    //用较为粗鄙语言表诉:即字符不匹配时回溯两层后对应的字符下标
           	}
           	else  k=nextval[k];    	
    	}
    
    }
    
    int KMPIndex1(SqString s,SqString t)    
    //修正的KMP算法
    //只是next换成了nextval
    {
    	int nextval[MaxSize],i=0,j=0;
    	GetNextval(t,nextval);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{	
    			i++;j++;	
    		}
    		else j=nextval[j];
    	}
    	if (j>=t.length)  
    		return(i-t.length);
    	else
    		return(-1);
    }
    

    剩下的话

    在写这篇博客时,我想起了编译原理老师讲过的一些知识,其实KMP算法的步骤与自动机有不少相似之处,有兴趣的朋友不妨联系对比一下。

    展开全文
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • KMP算法——很详细的讲解

    万次阅读 多人点赞 2018-09-09 10:52:23
    KMP算法(研究总结,字符串) KMP算法(研究总结,字符串) 前段时间学习KMP算法,感觉有些复杂,不过好歹是弄懂啦,简单地记录一下,方便以后自己回忆。 引入 首先我们来看一个例子,现在有两个字符串A和B,...
    原文地址:
    http://www.cnblogs.com/SYCstudio/p/7194315.html  
    

    KMP算法(研究总结,字符串)

    KMP算法(研究总结,字符串)

    前段时间学习KMP算法,感觉有些复杂,不过好歹是弄懂啦,简单地记录一下,方便以后自己回忆。

    引入

    首先我们来看一个例子,现在有两个字符串A和B,问你在A中是否有B,有几个?为了方便叙述,我们先给定两个字符串的值
    A=”abcaabababaa”
    B=”abab”
    那么普通的匹配是怎么操作的呢?
    当然就是一位一位地比啦。(下面用蓝色表示已经匹配,黑色表示匹配失败)
    此处输入图片的描述
    但是我们发现这样匹配很浪费!
    为什么这么说呢,我们看到第4步:
    此处输入图片的描述
    在第4步的时候,我们发现第3位上c与a不匹配,然后第五步的时候我们把B串向后移一位,再从第一个开始匹配。
    此处输入图片的描述
    这里就有一个对已知信息很大的浪费,因为根据前面的匹配结果,我们知道B串的前两位是ab,所以不管怎么移,都是不能和b匹配的,所以应该直接跳过对A串第二位的匹配,对于A串的第三位也是同理。

    或许这这个例子还不够经典,我们再举一个。

    A=”abbaabbbabaa”
    B=”abbaaba”

    在这个例子中,我们依然从第1位开始匹配,直到匹配失败:

    abbaabbbabba
    abbaaba
    我们发现第7位不匹配
    那么我们若按照原来的方式继续匹配,则是把B串向后移一位,重新从第一个字符开始匹配
    abbaabbbabba
    _abbaaba
    依然不匹配,那我们就要继续往后移咯。
    且住!
    既然我们已经匹配了前面的6位,那么我们也就知道了A串这6位和B串的前6位是匹配的,我们能否利用这个信息来优化我们的匹配呢?
    也就是说,我们能不能在上面匹配失败后直接跳到:
    abbaabbbabba
    ____abbaaba
    这样就可以省去很多不必要的匹配。

    KMP算法

    KMP算法就是解决上面的问题的,在讲述之前,我们先摆出两个概念:

    前缀:指的是字符串的子串中从原串最前面开始的子串,如abcdef的前缀有:a,ab,abc,abcd,abcde
    后缀:指的是字符串的子串中在原串结尾处结尾的子串,如abcdef的后缀有:f,ef,def,cdef,bcdef

    KMP算法引入了一个F数组(在很多文章中会称为next,但笔者更习惯用F,这更方便表达),F[i]表示的是前i的字符组成的这个子串最长的相同前缀后缀的长度!
    怎么理解呢?
    例如字符串aababaaba的相同前缀后缀有a和aaba,那么其中最长的就是aaba。

    KMP算法的难理解之处与本文叙述的约定

    在继续我们的讲述之前,笔者首先讲一下为什么KMP算法不是很好理解。
    虽然说网上关于KMP算法的博客、教程很多,但笔者查阅很多资料,详细讲述过程及原理的不多,真正讲得好的文章在定义方面又有细微的不同(当然,真正写得好的文章也有,这里就不一一列举),比如说有些从1开始标号,有些next表示的是前一个而有些是当前的,通读下来,难免会混乱。
    那么,为了防止读者在接下来的内容中感到和笔者之前学习时同样的困惑,在这里先对下文做一些说明和约定。

    1.本文中,所有的字符串从0开始编号
    2.本文中,F数组(即其他文章中的next),F[i]表示0~i的字符串的最长相同前缀后缀的长度。

    F数组的运用

    那么现在假设我们已经得到了F的所有值,我们如何利用F数组求解呢?
    我们还是先给出一个例子(笔者用了好长时间才构造出这一个比较典型的例子啊):
    A=”abaabaabbabaaabaabbabaab”
    B=”abaabbabaab”
    当然读者可以通过手动模拟得出只有一个地方匹配
    abaabaabbabaaabaabbabaab
    那么我们根据手动模拟,同样可以计算出各个F的值

    B=”a b a a b b a b a a b “
    F= 0 0 1 1 2 0 1 2 3 4 5(2017.7.25 Update 这里之前有一个错误,感谢@ 歌古道指正)(2017.7.29 Update 好吧,这里原来还有一个错误,已经更正啦感谢@iwangtst)

    我们再用i表示当前A串要匹配的位置(即还未匹配),j表示当前B串匹配的位置(同样也是还未匹配),补充一下,若i>0则说明i-1是已经匹配的啦(j同理)。
    首先我们还是从0开始匹配:
    此处输入图片的描述
    此时,我们发现,A的第5位和B的第5位不匹配(注意从0开始编号),此时i=5,j=5,那么我们看F[j-1]的值:

    F[5-1]=2;

    这说明我们接下来的匹配只要从B串第2位开始(也就是第3个字符)匹配,因为前两位已经是匹配的啦,具体请看图:
    此处输入图片的描述
    然后再接着匹配:
    此处输入图片的描述
    我们又发现,A串的第13位和B串的第10位不匹配,此时i=13,j=10,那么我们看F[j-1]的值:

    F[10-1]=4

    这说明B串的0~3位是与当前(i-4)~(i-1)是匹配的,我们就不需要重新再匹配这部分了,把B串向后移,从B串的第4位开始匹配:
    此处输入图片的描述

    这时我们发现A串的第13位和B串的第4位依然不匹配
    此处输入图片的描述
    此时i=13,j=4,那么我们看F[j-1]的值:

    F[4-1]=1

    这说明B串的第0位是与当前i-1位匹配的,所以我们直接从B串的第1位继续匹配:
    此处输入图片的描述
    但此时B串的第1位与A串的第13位依然不匹配
    此处输入图片的描述
    此时,i=13,j=1,所以我们看一看F[j-1]的值:

    F[1-1]=0

    好吧,这说明已经没有相同的前后缀了,直接把B串向后移一位,直到发现B串的第0位与A串的第i位可以匹配(在这个例子中,i=13)
    此处输入图片的描述
    再重复上面的匹配过程,我们发现,匹配成功了!
    此处输入图片的描述

    这就是KMP算法的过程。
    另外强调一点,当我们将B串向后移的过程其实就是i++,而当我们不动B,而是匹配的时候,就是i++,j++,这在后面的代码中会出现,这里先做一个说明。

    最后来一个完整版的(话说做这些图做了好久啊!!!!):
    此处输入图片的描述

    F数组的求解

    既然已经用这么多篇幅具体阐述了如何利用F数组求解,那么如何计算出F数组呢?总不能暴力求解吧。

    KMP的另外一个巧妙的地方也就在这里,它利用我们上面用B匹配A的方法来计算F数组,简单点来说,就是用B串匹配B串自己!
    当然,因为B串==B串,所以如果直接按上面的匹配,那是毫无意义的(自己当然可以完全匹配自己啦),所以这里要变一变。

    因为上面已经讲过一部分了,先给出计算F的代码:

    for (int i=1;i<m;i++)
    {
        int j=F[i-1];
        while ((B[j+1]!=B[i])&&(j>=0))
            j=F[j];
        if (B[j+1]==B[i])
            F[i]=j+1;
        else
            F[i]=-1;
    }

    首先可以确定的几点是:

    1.F[0]=-1 (虽说这里应该是0,但为了方便判越界,同时为了方便判断第0位与第i位,程序中这里置为-1)
    2.这是一个从前往后的线性推导,所以在计算F[i]时可以保证F[0]~F[i-1]都是已经计算出来的了
    3.若以某一位结尾的子串不存在相同的前缀和后缀,这个位的F置为-1(这里置为-1的原因同第一条一样)

    重要!:另外,为了在程序中表示方便,在接下来的说明中,F[i]=0表示最长相同前缀后缀长度为1,即真实的最长相同前缀后缀=F[i]+1。(重要的内容要放大)
    为什么要这样设置呢,因为这时F[i]代表的就不仅仅与前后缀长度有关了,它还代表着这个前缀的最后一个字符在子串B中的位置。

    所以,之前上面列出的F值要变一下(这里用’_’辅助对齐):

    B=”a _b a a b _b a b a a b “
    F= -1 -1 0 0 1 -1 0 1 2 3 4

    那么,我们同样可以推出,求解F的思路是:看F[i-1]这个最长相同前缀后缀的后面是否可以接i,若可以,则直接接上,若不可以,下面再说。
    举个例子:
    还是以B=”abaabbabaab”为例,我们看到第2个。

    B=”a b a a b b a b a a b”
    F=-1 -1

    此时这个a的前一个b的F值为-1,所以此时a不能接在b的后面(b的相同最长前缀后缀是0啊),此时,j=-1,所以我们判断B[j+1]与B[2],即B[0]与B[2]是否一样。一样,所以F[2]=j+1=0(代表前0~2字符的最长相同前缀后缀的前缀结束处是B[0],长度为0+1=1)。

    再来看到第3个:

    B=”a b a a b b a b a a b”
    F=-1 -1 0

    开始时,j=F[3-1]=0,我们发现B[j+1=1]!=B[i=3],所以j=F[j]=-1,此时B[j+1=0]==B[i=3],所以F[3]=j+1=0。

    最后举个例子,看到第4个

    B=”a b a a b b a b a a b”
    F=-1 -1 0 0

    j首先为F[4-1]=0,我们看到B[j+1=1]==B[i],所以F[i]=j+1=1。

    后面的就请读者自己慢慢推导了。再强调一遍,我们这样求出来的F值是该最长相同前缀后缀中的前缀的结束字符的数组位置(从0开始编号),如果要求最长相同前缀后缀的长度,要输出F[i]+1。

    代码

    求解F数组:

    for (int i=1;i<m;i++)
    {
        int j=F[i-1];
        while ((B[j+1]!=B[i])&&(j>=0))
            j=F[j];
        if (B[j+1]==B[i])
            F[i]=j+1;
        else
            F[i]=-1;
    }

    利用F数组寻找匹配,这里我们是每找到一个匹配就输出其开始的位置:

    while (i<n)
    {
        if (A[i]==B[j])
        {
            i++;
            j++;
            if (j==m)
            {
                printf("%d\n",i-m+1);//注意,这里输出的位置是从1开始标号的,如果你要输出从0开始标号的位置,应该是是i-m.这份代码是我做一道题时写的,那道题要求输出的字符串位置从1开始标号.感谢@Draymonder指出了这个疏漏,更多内容请看评论区
                j=F[j-1]+1;
            }
        }
        else
        {
            if (j==0)
                i++;
            else
                j=F[j-1]+1;
        }
    }
    展开全文
  • KMP算法—终于全部弄懂了

    万次阅读 多人点赞 2019-03-22 21:00:45
    详细讲解KMP算法,并对难点 k=next[k] 这条语句重点描述
  • KMP算法图片详解

    2021-03-05 10:16:50
    KMP算法,解决字符串中的包含问题,时间复杂度O(M+N)。例:str1(长度为M)和str2(长度为N)为两个字符串,判断str1中是否包含str2。 解决办法: 暴力破解: 从开头开始一直向下配,如果配不上从下一个字符继续配...
  • KMP算法的工作流程介绍

    千次阅读 2014-06-02 19:49:56
    最近又想起了KMP算法,原来一直没搞明白工作原理,现在...推荐理由:简单明了,是我看过介绍KMP算法流程的所有文章中,最易懂的一篇(这篇文章仅仅是介绍了KMP算法的工作流程,并没有介绍KMP算法为什么当初这么设计!)
  • KMP算法详解

    万次阅读 多人点赞 2019-04-25 22:05:03
    KMP算法是一种字符串模式匹配算法,不同的来源讲解方式也不一样,很容易混乱,在这里以一种特殊的方式来讲解KMP算法,希望大家不再被这个问题所困扰。 一. 一些基础问题 什么是字符串的模式匹配? 给定两个串S=...
  • 目录1.1 串1.2 Brute Force1.3 KMP算法1.4 next数组构造 1.1 串 KMP算法主要是用来解决串的匹配问题,为此,在学习KMP之前我们先来了解一下串的相关知识。 串是由若干个字符组成的有限序列,也就是我们熟悉的字符串。...
  • KMP算法

    2021-10-14 19:28:58
    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
  • KMP 算法图文详解

    千次阅读 2017-05-16 10:53:35
    1、暴力匹配算法假设我们现在面临这样一个问题,有一个文本串 S 和一个模式串 P,现在要查找P在S中的位置,那么应该如何查找呢?我们很容易就想到暴力匹配的方法,假设现在文本串S匹配到 i 位置,模式串 P 匹配到 j ...
  • KMP算法学习为什么用KMP算法暴利匹配算法KMP算法思路研究子串流程图 为什么用KMP算法 KMP是一种高效的模式匹配的一种算法 模式匹配,说直白就是找寻子字符串在主字符串的位置 (其实KMP这三个字没啥意义,这算法是3...
  • kmp算法

    2021-09-17 16:15:44
    kmp算法 本人理解敲出来的,有些长,如果想要理解请认真看完 那么如何进行匹配呢,若文本串str1为aabaaaabaaf,模式串str2为aabaaf 上面求出来aabaaf的next表为 010120 指针 i = 0, j = 0 (i为文本串指针, j为模式...
  • 常用十大算法_KMP算法

    千次阅读 多人点赞 2020-07-25 08:34:22
    KMP算法 FBI提示:KMP算法不好理解, 建议视频+本文+其他博客,别走马观花 KMP算法是用于文本匹配的算法,属于模式搜索(pattern Searching)问题的一种算法,在讲KMP算法之前,传统的匹配字符算法是暴力匹配(BF...
  • 扩展KMP算法

    2017-08-21 11:47:05
    作者:刘毅  ...文章采用[知识共享署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议]进行许可 扩展 KMP 算法 ... KMP 算法的扩展,即扩展 KMP 算法。 问题定义:给定两个字符串 S 和 T(长度分别为 n 和 m
  • KMP算法分析

    2019-02-21 17:38:58
    KMP算法分析 一、KMP算法 1.1 概述 KMP(D.E.Knuth,J.H.Morris,V.R.Pratt)算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,称之为克努特–莫里斯–普拉特算法,简称KMP算法。 一般匹配字符串时,我们从目标...

空空如也

空空如也

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

kmp算法流程图