精华内容
下载资源
问答
  • 4.3.2 KMP 算法 KMP 算法是 D.E.Knuth J.H.Morris 和 V .R.Pratt 共同提出的 , 简称 KMP 算法算法较 BF 算法有较 大改进 , 主要是消除了主串指针的回溯 , 从而使算法效 率有了某种程度的提高 所谓 真子串 是指模式...
  • 数据结构KMP算法配图详解(超详细)

    千次阅读 多人点赞 2020-02-18 22:02:42
    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...

    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;

    a b c a b c m n
    next[0] next[1] next[2] next[3] next[4] next[5] next[6] next[7]
    -1 0 0 0 1 2 3 0

    本例中的蓝色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数组分别为:

    下标 0 1 2 3 4 5 6 7
    子串 a b a b a a a b
    next -1 0 0 1 2 3 1 1
    nextval -1 0 -1 0 -1 3 1 0

    我们来分析下代码:

    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算法解析 KMP算法是一种匹配算法,用来进行匹配查找。 通过在子串的每一位都设置一个与之对应的回溯数组下标,降低算法的时间复杂度。 每一个需要查找的子串,该算法都会给它生成一个与之相对于的next数组,用来...

    KMP算法解析

    KMP算法是一种匹配算法,用来进行匹配查找。
    通过在子串的每一位都设置一个与之对应的回溯数组下标,降低算法的时间复杂度。
    每一个需要查找的子串,该算法都会给它生成一个与之相对于的next数组,用来进行回溯。

    假设需要查找的子串为:string S=“aaababa”//该串首位也用来存放数据
    生成的next数组为0012010//代表数组下标

    假如数组是匹配到了S[3]才出现匹配失败,这代表前面的S[0],S[1],S[2]都匹配成功了。S[0],S[1]和S[1],S[2]是一样的,都是aa,所以现在主串只需要和S[2]进行匹配。

    设置子串的next数组的时候,只需要看该数位前面的数据,头和尾一样的数据有多少,回溯的位置就是一样的数据段中串头数据段的下一位!
    子串ababc,那么next[4]=2;因为c前面的串头ab和串为ab一样,所以只需从一样的前面部分的下一位开始匹配。
    子串ababac,那么next[5]=3,因为c前面串头aba和串为aba一样,同理即可!
    子串aab,next[1]=0;next[2]=1;前面是因为没有形成串头串尾,后面的同理即可!
    (中间的元素可重复利用,但是子串的串头和串尾不能是同一个元素)

    假如子串为S;主串为T。子串与主串进行匹配的时候,如果主串T[j]匹配到了子串S[i]出现匹配失败,那么子串的数组下标i=next[i],然后继续和T[j]进行匹配,一直重复,直到匹配成功或者匹配到了子串的第一个数据依然不相等,则令主串的数组下标指向自增(j++),也就是主串的下一个元素继续和子串进行匹配,一直重复直到找到该子串或者主串结束。

    字符串首位存放字符长度

    #include<iostream>
    using namespace std;
    int getNext(string s, int* next)/获取next数组
    {
    	int i = 0, j = 1;//i用来代表该回溯的数组下标
    	next[1] = 0;
    	while (j<(s[0]-48))//因为传进来的是字符,所以想要获得自己想要的数需要在此基础上-48,下面同理
    	{
    		if (i==0||s[i] == s[j])
    		{
    			i++;
    			j++;
    			if (s[i]==s[j])
    			{
    				next[j] = next[i];
    			}
    			else
    			{
    				next[j] = i;
    			}
    		}
    		else
    		{
    			i = next[i];
    		}
    	}
    	return 0;
    }
    int search(string t, string s, int pos)//t是主串,s是匹配串,pos是开始匹配的位置
    {
    	int j = pos;
    	int i = 1;
    	int next[255];
    	getNext(s, next);
    	while (j <= (t[0]-48) && i <= (s[0]-48))
    	{
    		if (i==0||t[j] == s[i])//如果匹配到s[1]还匹配不成功的话,主串就指向下一个元素
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i = next[i];
    		}
    	}
    	if (i > (s[0]-48))//此时t[j]指的是主串刚匹配完最后一个子串数据的下一个单位
    	{
    		return  j - (s[0]-48);//减去子串长度得到匹配的首地址
    	}
    	else
    	{
    		return 0;
    	}
    }
    int main()
    {
    	string s = "8aaababaa";//前面的8指的是后面的字符串长度
    	string t = "3baa";
    	int a;
    	a=search(s, t, 0);//如果返回的数是0,则代表主串中没有所要查找的子串
    	if (a == 0)
    	{
    		cout << "查找失败,主串中没有该子串!";
    	}
    	else
    	{
    		cout << "所查找的子串的首元素数组下标为:" << a << endl;
    	}
    	return 0;
    }
    
    

    字符串全部用来存放数据

    #include<iostream>
    using namespace std;
    int getNext(string s, int *next)//获取next数组
    {
    	int i = 0, j = 1;//i用来代表该回溯的数组下标,//j代表设置next[j]的值
    	next[0] = 0;
    	while (j<s.size())//判断串中的元素都设置了回溯值
    	{
    		if (s[i] == s[j])//如果两者相等,那么主串的元素和s[i],s[j]比较的结果都是一样的,所以直接和最前面那个比较就行了。
    		{
    			next[j] = next[i];
    			i++;
    			j++;
    		}
    		else if (i == 0 && s[i] != s[j])//i一直回溯到第一个还是和s[j]不一样,那么设置next[j]就为i,并且j自增,开始设置下一个值的回溯值
    		{
    			next[j] = i;
    			j++;
    		}
    		else //如果上面两个条件都没进入,代表既不相等,也还没到第一个匹配值,继续往前回溯
    		{
    			i = next[i];
    		}
    	}
    	return 0;
    }
    int search(string t, string s, int pos)//t是主串,s是匹配串,pos是开始匹配的位置
    {
    	int j = pos;
    	int i = 0;
    	int next[255];
    	getNext(s, next);
    	while (j <= t.size() && i <= s.size())//主串中没有该子串,或者子串匹配完毕就退出。
    	{
    		if (t[j] == s[i])//两个数据相等,就一起对比下一个数据
    		{
    			i++;
    			j++;
    		}
    		else if (i == 0 && t[j] != s[i])//如果匹配到s[0]还匹配不成功的话,主串就指向下一个元素
    		{
    			j++;
    		}
    		else//如果上面的判断都没进入,子串就继续往前回溯
    		{
    			i = next[i];
    		}
    	}
    	if (i > s.size())//此时t[j]指的是主串刚匹配完最后一个子串数据的下一个单位
    	{
    		return  j - s.size();//主串上面退出时j所代表的下标刚好是匹配完子串之后的下一个元素,减去子串长度得到主串中与子串相匹配的首地址
    	}
    	else
    	{
    		return 0;
    	}
    }
    int main()
    {
    	string s = "asdfasgcaadaaaabbaaas";//主串
    	string t = "aaaabba";//子串
    	int a;
    	a=search(s, t, 0);
    	cout << "所查找的子串的首元素数组下标为:" << a << endl;
    	int i = 0;
    	while (i<t.size())
    	{
    		cout << s[a];
    		a++;
    		i++;
    	}
    	return 0;
    }
    
    
    展开全文
  • 大名鼎鼎的KMP算法 来吧今天我们一起搞懂它!???? 首先不太清楚KMP算法的可以戳这里!百度百科欢迎您~ KMP算法简介: KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主...

    大名鼎鼎的KMP算法

    来吧今天我们一起搞懂它!💪
    首先不太清楚KMP算法的可以戳这里!百度百科欢迎您~

    KMP算法简介:
    KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。(来源百度)

    可以看到KMP算法它的优势就是不回溯!
    那么它怎么做到不回溯呢?我们一起来看看吧!如果你对普通算法清楚的话,请直接滑到KMP算法开始处~

    普通的字符串匹配

    如上图,上面的长串是被查找串,我们称源串;下面的短串"abcd" 是我们要查找的字符串,我们称子串。i 和 j 分别是源串和子串的查找下标。我们可以看到当下标 i 和 j 查到的内容不相等时,下标 i 立马回溯到第二个空间,而下标 j 也重新开始匹配。当下标 i 和 j 查到的内容再次不相等时,下标 i 立马回溯到第三个空间,下标 j 重新开始匹配。如果相等则继续向后比较,直到下标 j 所查找的空间值为0时,也就是 ‘\0’ --0结束标志,那么就算是找到了!当然有一些条件我没有在这里说,这里仅作介绍。具体代码里有。

    上述方法看似没有问题,实则不然,当遇到一些神奇的字符串时,它就吃了大亏啦!下面两个字符串我们肉眼可见其实下标 i 可以不用回溯的,完全可以接着比,只要我们找到里面的玄机就OK!

    KMP算法开始

    我们以↖左上图为例讲解

    按照普通方法比较,下标 i 和 j 比较到下图位置,他们比较的字符开始不相同了。

    问:子串从失配点开始,左边存在最长多少个字符,与该子串最开始的字符是相同的?
    答:5个。

    此时,i 和 j 前面的字符都相等,我们观察子串,下标 j (失配点)前面,我们可以观察到从左至右aadaa出现了两次,且是相等的;因为绿框中的aadaa与红框中的aadaa已经比较过了,是相等的,且黄框与绿框中的字符串也相等,所以黄框与红框中的字符串相等。

    因为子串从失配点开始,左边存在最长5个字符,与该子串最开始的字符是相同的,所以我们将下标 j 移至下标为 5 的地方与 i 继续比较,这样做 i 不用回溯,也不会漏掉我们要找的字符串,并且前面比过的字符也不用再比一遍了!

    我们继续用这种方法匹配;

    我们看到这里找到了!比普通方法不知快了多少步!

    综上,我们发现使用这种方法 i 可以不用回溯,j 每次回溯的下标恰好等于失配点左边最多的相同字符数!

    那么这个方法具体该怎么去用呢?如果要用这种方法,势必得全面考虑,也就是说,我们必须考虑每一个字符失配之后的操作!

    aadaadaaaadaa
    这是我们的子串,我们必须算出当子串中每一个字符为失配点时,下标 j 将会移动到哪个下标去|才能保证不丧失可能存在的匹配!其实这一步方法就是前面提到过的:子串从失配点开始,左边存在的字符|与该子串最开始的字符相同的最长字符个数。
    我们需要构造一个next[]数组,它的长度就是子串数组的长度,用next[]数组来存储子串字符的回溯下标。

    之所以要取最长相同字符个数是因为如果取短了,可能会错过我们要匹配的字符串!
    举例:如下图,其实我们如果不取最长相同字符的话,也可以取"aa",也就是 j 回溯到下标为2的地方和 i 继续比较。

    看下图,我们发现中间的一些字符被跳过了,万一以它开头的字符串就是我们要找的呢,那我们就完美的错过了心心念念的字符串!可见,一定要找最长的相同字符个数!

    next[]数组的手工过程(代码角度)

    下面我们就开始愉快的手工过程~
    注意:图中的下标 i, j 不再是源串与子串比较时的下标了,而是计算next[]数组时,子串的两个下标!图中的sub[]数组就是存储子串的数组!因为下标为0,1时,失配点左边最多的相同字符数都为0 。所以下标 i 直接从2开始。

    i 从 2 开始,j 从 0 开始,若 以(i - 1)为下标的元素与以 j 为下标的元素相同,则 j ++ ,并且把 j 的值赋值给 next[ i ],然后 i++ ;若不相等,则执行( j = next[ j ] ; )操作,然后继续比,相同了就继续 j ++ ,并且把 j 的值赋值给 next[ i ],然后 i++;不相同则执行( j = next[ j ] ; ) 操作;若 j 已经为0了,就不必再执行( j = next[ j ] ; ) 操作了,因为再怎么执行也是0 啊,而且死循环的!这时候直接把 j 的值赋值给 next[ i ] ,然后 i++ 就行了。请结合文字和下面图片一起看!

    图片中 【 j = next[ j ] 】这是一步很骚的操作!大家应该也感受到了!这个伟大算法的精妙之处!

    当所有的下标计算完成后,大名鼎鼎的next[]数组就完成了,记录它的目的是:若当前下标的字符失配,我们就可以知道当前下标应该回溯到哪个下标位置继续与源串下标为i 的字符进行比较。(j 回溯,不是 i)

    这个数组就是KMP算法的核心!有了这个数组,一但字符失配,就去数组里查查下标 j 该回溯到哪里继续与下标 i 比,而下标 i 就可以做到一直屹然不动!当然有一些不用继续比较的条件,我这里没有说,在代码里,大家一看就懂啦!

    一年一度的代码环节

    kmp.h

    #ifndef _MEC_KMP_H_
    #define _MEC_KMP_H_
    
    int KMPSearch(const char *str, const char *sub);
    
    #endif
    
    

    kmp.c

    #include <stdio.h>
    #include <malloc.h>
    #include <string.h>
    
    #include "mec.h"
    #include "KMP.h"
    
    static void getNext(const char *str, int *next);
    static int searchMainBody(const char *str, const 
    		char *sub, int *next, int strLen, int subLen);
    
    static void getNext(const char *str, int *next) {
    	int i = 2;
    	int j = 0;
    
    	while (str[i]) {
    		if (str[i - 1] == str[j] || 0 == j) {
    			next[i++] = (j == 0 ? 0 : ++j);
    			continue;
    		}
    		j = next[j];
    	}
    
    	
    }
    
    static int searchMainBody(const char *str, const char *sub,
    		int *next, int strLen, int subLen) {
    	int i = 0;
    	int j = 0;
    
    	while ((strLen - i) >= (subLen - j)) {
    		if (0 == sub[j]) {
    			return i - subLen;
    		}
    		if (str[i] == sub[j]) {
    			++i, ++j;
    			continue;
    		}
    		if (0 == j) {
    			++i;
    			continue;
    		}
    		j = next[j];
    	}
    
    	return NOT_FOUND;
    }
    
    int KMPSearch(const char *str, const char *sub) {
    	int strLen = strlen(str);
    	int subLen = strlen(sub);
    	int *next = NULL;
    	int result;
    
    	if (NULL == str || NULL == sub 
    			|| subLen <= 0 || subLen > strLen) {
    		return NOT_FOUND;
    	}
    
    	next = (int *) calloc(sizeof(int), subLen);
    	if (subLen > 2) {
    		getNext(sub, next);
    	}
    
    	for(int i = 0;i < subLen;i++){
            printf("%d ",next[i]);
        }
    
        printf("hh %d ",next );
    
        printf("\n");
    
    	result = searchMainBody(str, sub, next, strLen, subLen);
    
    	free(next);
    
    	return result;
    }
    
    

    test.c

    #include <stdio.h>
    
    #include "KMP.h"
    
    int main() {
    	char s[80];
    	char sub[80];
    	int index;
    
    	printf("请输入原串:");
    	gets(s);
    	printf("请输入子串:");
    	gets(sub);
    
    	index = KMPSearch(s, sub);
    	printf("%d\n", index);
    
    	return 0;
    }
    
    

    “mec.h” 要看的话点这里! 直接滑到底看~

    结果展示:
    在这里插入图片描述

    展开全文
  • 一、前言相信不少朋友都有用过记事本、word等文本编辑器,在这些文本编辑器当中如果我们想要快速获取我们想要的文字,这些软件是有提供这样一种方式的,就是“查找”,按住...现在比较常用的匹配算法是KMP算法,当然...

    一、前言

    相信不少朋友都有用过记事本、word等文本编辑器,在这些文本编辑器当中如果我们想要快速获取我们想要的文字,这些软件是有提供这样一种方式的,就是“查找”,按住ctrl+F就会弹出方框,然后输入自己想要查找的文本就可以找到了。事实上这就是一种字符串匹配算法,你输入的字符串就是匹配串,word里面长篇的文本就是主串,然后在主串里面找到你的匹配串。现在比较常用的匹配算法是KMP算,当然还有BF算法,不过BF算法效率比较低,现在一般都是用KMP算法,是数据结构里面的一种。

    二、BF算法简介

    在介绍KMP算法之前还是先简单介绍下BF算法,这是一种比较传统的算法,也叫暴力匹配算法,因为真的很暴力,虽然也可以找出匹配的位置,但是效率比较低,如果文本内容有很多的话那就麻烦了。它采用的是一种回溯法。

    过程是:

    假设现在主串是abcdefgh,模式串是123,这个时候如果要匹配的话,先把这两个字符串头头相对,然后匹配第一个元素:

    462db5017c780b17a9d9405d1264caa2.png

    接着匹配第二个元素:

    b2e6a64c2bb5dac519675e4cb7185c98.png

    匹配第三个元素:

    5370274270993082ce22fa957ed601c3.png

    这个时候你会发现把模式串3个元素全都匹配完成之后发现最后一个失配了,接下来模式串就要向右移动一格了:

    05c49d9544fedb59b20808ab497a7298.png

    移动一个后按部就班跟刚才一样,从第一个比较起,然后第二个,直到最后一个,如果匹配完全部元素后发现不一致,那么模式串将继续右移一格,每次移动一格之后,判断位置都从模式串的第一个判断起,直到模式串的最后一个。相信聪明的你现在已经知道规律了,那用代码如何实现呢?如下:

    public class Test {public static void main(String[] args) {
    String str1="abcdefg";String str2="bcd";BF(str1, str2);}public static void BF(String str1,String str2)
    {int index=0,i=0,j=0;
    while
    (i {if(str1.charAt(i)==str2.charAt(j))
    {
    i++;j++;}else{
    index++;i=index;j=0;}if(j>=str2.length())
    {
    System.out.println("匹配成功,索引为:"+(i-str2.length()));}
    }
    }
    }

    三、BF算法

    已经给大家介绍完BF算法了,现在步入正题。我们已经知道BF算法的模式串一般发现有跟主串不一样的元素,那么整个模式串就要向右移动一格,然后从自己的第一个元素判断起到发现不一样的或都一样到最后一格元素。但事实上,细心的我们会发现其实没必要每次都向右移动一格,因为效率太低了,有时候模式串是可以直接向右移动好几格,且移动之后也没必要从模式串的第一个元素判断起,因为明知道不可能匹配就没必要去判断了,效率就高了很多。那当发现模式串和主串有不一样的元素之后,模式串向右移动多少格以及移动之后从哪里判断起才是合适的呢?这个时候我们要引入部分匹配表

    这张表是如何来的这里先不说,放到最后,因为这张表实在关键,这里先会看会用就行了。

    8e65512fd03ec783cf234abd9de631de.png

    以上就是部分匹配表,上面代表的是字符串,下面代表的是如果这个位置失配后那么模式串的哪个索引位置要顶过来。字符串一般首个元素的索引是0,A下面的0代表如果这个位置失配了,那么模式串的0索引位置处要右移顶过来,移动到失配地方处。如果是1的话就代表索引为1的元素要顶过来。

    四、next数组

    其实,上面的部分匹配表是有专门名称的,叫next数组,因为它跟模式串每一个元素都是一一对应的,接下来介绍下next数组,介绍next数组之前得先介绍下前缀后缀

    fa247cb200f608bda9e9bf7b5ab3d531.png

    那next数组有什么用呢?答案如下:

    a6f4ed73b36b0b01a5de88b3f95d6c9f.png

    综上,next数组就是模式串的一格附属工具,记录着失配位置失配后接下来要匹配的位置。

    五、next数组的求法

    讲完next数组后该讲讲next数组怎么求了。

    主串:abababbbab

    • 首先next[0]=-1,next[1]=0;

    • 之后每一位j的next求解: 
      比较j-1字符与next[j-1]是否相等, 
      如果相等则next[j]=next[j-1]+1, 
      如果不相等,则比较j-1字符与next[next[j-1]]是否相等, 
      1) 如果相等则next[next[j-1]]+1, 
      2)如果不相等则继续以此下去,直到next[…]=-1,则next[j]=0.

    通俗易懂的话来说就是你要求解当前位的next值,则看前一位与前一位next所在位字符是否相等,相等则当前位的next等于前一位next+1,如果不等就找前一位next的next与前一位比较,如果相等,当前位的next等于那个与前一位字符相等的字符所在位置+1,如果还是不相等,则以此类推,直到出现比较位为next[]=-1,那当前位的next就等于-1。 
    然而在算法求解的时候,我们应该这样去理解,求解下一位的next等于当前位与当前位的next比较。算法如下:

    public static void getNext(int[]next,String str)
    {
    next[0]=-1;
    int
    k=-1,j=0;System.out.println(str);
    while
    (j1
    )
    {if(k==-1 || str.charAt(j)==str.charAt(k))
    {
    j++;k++;next[j]=k;}else{
    k=next[k];}
    }
    }

    这样得到的就是模式串对应的next数组了。

    六、完整的KMP算法

    import java.util.ArrayList;
    import
    java.util.List;
    import
    java.util.Scanner;
    public class
    KMP {public static void main(String[] args) {
    System.out.println("请输入字符串:");Scanner sc=new Scanner(System.in);String str1=sc.nextLine();System.out.println("请输入匹配串:");String str2=sc.nextLine();
    int
    []next=new int[str2.length()];getNext(next, str2);
    for
    (int i=0;i;
    i++)
    {
    System.out.print(next[i]+" ");}
    List pos=new ArrayList();Match(str1, str2, next, pos);System.out.println();System.out.println(pos);}public static void Match(String str1,String str2,int[]next,Listpos)
    {int j=0,s=0;
    while
    (j {if(s==-1 || str1.charAt(j)==str2.charAt(s))
    {
    j++;s++;
    if
    (s>=str2.length())
    {
    pos.add(j-str2.length());System.out.println("length="+(j-str2.length()));s=0;}
    }else{
    s=next[s];}
    }
    }public static void getNext(int[]next,String str)
    {
    next[0]=-1;
    int
    k=-1,j=0;System.out.println(str);
    while
    (j1)
    {if(k==-1 || str.charAt(j)==str.charAt(k))
    {
    j++;k++;next[j]=k;}else{
    k=next[k];}
    }
    }
    }

    七、KMP算法总结

    KMP算法刚开始学的时候确实有点难度,但事实上数据结构都这样的,代码本身不重要,模型才是重要的,代码和算法最终只是实现方法而已,所以要多花时间去体会下模型的逻辑思维和结构。

    2f2970f28efd3b1b1c737633f8084098.png

    展开全文
  • KMP算法优于BF算法的地方是指针不回溯,利用已经比较过的部分,将模式串向右移动尽可能远的距离,在继续比较。 KMP算法的核心就是构建一个next[]数组,以这个数组来决定移动的距离。 在此之前先引入 公共前缀后缀...
  • KMP 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,但是确实有点复杂。 很多读者抱怨 KMP 算法无法理解,这很正常,想到大学教材上关于 KMP 算法的讲解,也不知道有多少未来的 Knuth、...
  • 本文主要对KMP算法进行介绍 KMP算法是一个序列匹配的算法,比如有两个序列s1和s2,想知道s1中是不是有一个和s2相同的子串,如果有,返回匹配的起始位置。 最直觉最暴力的方法就是依次从s1的任何一个位置去匹配s2,...
  • 看了一晚上终于明白这个KMP算法是什么意思,果然只要是想学习,就能学会呀,谢谢这两篇博客 见网址http://www.cnblogs.com/SYCstudio/p/7194315.html和https://blog.csdn.net/f1033774377/article/details/82556438...
  • KMP算法详解

    2019-04-21 14:46:37
    KMP算法详解KMP的next串手算求法 我会结合代码对KMP算法进行详细讲解。由于编代码和做数据结构的题不一样所以,我分两部分对KMP进行讲解。 KMP的next串手算求法 书上对next串求法的定义是这样的: next[j]={0,j=1Max...
  • next数组表示字符串前后缀匹配的最大长度。是KMP算法的精髓所在。可以起到决定模式字符串右移多少长度以...详解KMP算法:https://www.cnblogs.com/yjiyjige/p/3263858.html //我觉得算法部分,这篇讲得最好,优...
  • 数据结构详解KMP算法

    千次阅读 2017-04-13 17:47:58
    详解KMP算法

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 220
精华内容 88
热门标签
关键字:

数据结构kmp算法详解

数据结构 订阅