kmp算法数据结构_数据结构kmp算法 - CSDN
  • KMP算法详解

    2019-04-26 20:05:50
    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;
    }
    
    展开全文
  • 最好的办法是先搞清楚它所用的数据结构是什么,再搞清楚怎么用,最后为什么的问题就会有恍然大悟的感觉。我试着从这个思路再介绍一下。大家只需要记住一点,PMT是什么东西。然后自己临时推这个算法也是能推出来的,...
    有些算法,适合从它产生的动机,如何设计与解决问题这样正向地去介绍。但KMP算法真的不适合这样去学。最好的办法是先搞清楚它所用的数据结构是什么,再搞清楚怎么用,最后为什么的问题就会有恍然大悟的感觉。我试着从这个思路再介绍一下。大家只需要记住一点,PMT是什么东西。然后自己临时推这个算法也是能推出来的,完全不需要死记硬背。KMP算法的核心,是一个被称为部分匹配表(Partial Match Table)的数组。我觉得理解KMP的最大障碍就是很多人在看了很多关于KMP的文章之后,仍然搞不懂PMT中的值代表了什么意思。这里我们抛开所有的枝枝蔓蔓,先来解释一下这个数据到底是什么。对于字符串“abababca”,它的PMT如下表所示:

    就像例子中所示的,如果待匹配的模式字符串有8个字符,那么PMT就会有8个值。

    我先解释一下字符串的前缀和后缀。如果字符串A和B,存在A=BS,其中S是任意的非空字符串,那就称B为A的前缀。例如,”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”},我们把所有前缀组成的集合,称为字符串的前缀集合。同样可以定义后缀A=SB, 其中S是任意的非空字符串,那就称B为A的后缀,例如,”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”},然后把所有后缀组成的集合,称为字符串的后缀集合。要注意的是,字符串本身并不是自己的后缀。

    有了这个定义,就可以说明PMT中的值的意义了。PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如,对于”aba”,它的前缀集合为{”a”, ”ab”},后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”},那么长度最长的元素就是字符串”a”了,长 度为1,所以对于”aba”而言,它在PMT表中对应的值就是1。再比如,对于字符串”ababa”,它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”},它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}, 两个集合的交集为{”a”, ”aba”},其中最长的元素为”aba”,长度为3。

    好了,解释清楚这个表是什么之后,我们再来看如何使用这个表来加速字符串的查找,以及这样用的道理是什么。如图 1.12 所示,要在主字符串"ababababca"中查找模式字符串"abababca"。如果在 j 处字符不匹配,那么由于前边所说的模式字符串 PMT 的性质,主字符串中 i 指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的。这是因为主字符串在 i 位失配,也就意味着主字符串从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。而我们上面也解释了,模式字符串从 0 到 j−1 ,在这个例子中就是”ababab”,其前缀集合与后缀集合的交集的最长元素为”abab”, 长度为4。所以就可以断言,主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的,即长度为 4 的后缀与前缀相同。这样一来,我们就可以将这些字符段的比较省略掉。具体的做法是,保持i指针不动,然后将j指针指向模式字符串的PMT[j −1]位即可。

    简言之,以图中的例子来说,在 i 处失配,那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位,它的前4位前缀和后4位后缀是相同的,所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

    有了上面的思路,我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j 位 失配,那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值,所以为了编程的方便, 我们不直接使用PMT数组,而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是,在把PMT进行向右偏移时,第0位的值,我们将其设成了-1,这只是为了编程的方便,并没有其他的意义。在本节的例子中,next数组如下表所示。


    int KMP(char * t, char * p) 
    {
    	int i = 0; 
    	int j = 0;
    
    	while (i < strlen(t) && j < strlen(p))
    	{
    		if (j == -1 || t[i] == p[j]) 
    		{
    			i++;
               		j++;
    		}
    	 	else 
               		j = next[j];
        	}
    
        if (j == strlen(p))
           return i - j;
        else 
           return -1;
    }
    

    好了,讲到这里,其实KMP算法的主体就已经讲解完了。你会发现,其实KMP算法的动机是很简单的,解决的方案也很简单。远没有很多教材和算法书里所讲的那么乱七八糟,只要搞明白了PMT的意义,其实整个算法都迎刃而解。

    现在,我们再看一下如何编程快速求得next数组。其实,求next数组的过程完全可以看成字符串匹配的过程,即以模式字符串为主字符串,以模式字符串的前缀为目标字符串,一旦字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。

    具体来说,就是从模式字符串的第一位(注意,不包括第0位)开始对自身进行匹配运算。 在任一位置,能匹配的最长长度就是当前位置的next值。如下图所示。






    求next数组值的程序如下所示:

    void getNext(char * p, int * next)
    {
    	next[0] = -1;
    	int i = 0, j = -1;
    
    	while (i < strlen(p))
    	{
    		if (j == -1 || p[i] == p[j])
    		{
    			++i;
    			++j;
    			next[i] = j;
    		}	
    		else
    			j = next[j];
    	}
    }
    作者:海纳
    链接:https://www.zhihu.com/question/21923021/answer/281346746
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    展开全文
  • 申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html什么是...KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字...

    申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html

    什么是KMP算法:

    KMP是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者!!

    KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。

     

    首先,对于这个问题有一个很单纯的想法:从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,将模式串向右移动一位。这有什么难的?

    我们可以这样初始化:

     

    之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动,如果不一致,如下图:

     

     

    A和E不相等,那就把i指针移回第1位(假设下标从0开始),j移动到模式串的第0位,然后又重新开始这个步骤:

     

    基于这个想法我们可以得到以下的程序:

    复制代码
     1 /**
     2 
     3  * 暴力破解法
     4 
     5  * @param ts 主串
     6 
     7  * @param ps 模式串
     8 
     9  * @return 如果找到,返回在主串中第一个字符出现的下标,否则为-1
    10 
    11  */
    12 
    13 public static int bf(String ts, String ps) {
    14 
    15     char[] t = ts.toCharArray();
    16 
    17     char[] p = ps.toCharArray();
    18 
    19     int i = 0; // 主串的位置
    20 
    21     int j = 0; // 模式串的位置
    22 
    23     while (i < t.length && j < p.length) {
    24 
    25        if (t[i] == p[j]) { // 当两个字符相同,就比较下一个
    26 
    27            i++;
    28 
    29            j++;
    30 
    31        } else {
    32 
    33            i = i - j + 1; // 一旦不匹配,i后退
    34 
    35            j = 0; // j归0
    36 
    37        }
    38 
    39     }
    40 
    41     if (j == p.length) {
    42 
    43        return i - j;
    44 
    45     } else {
    46 
    47        return -1;
    48 
    49     }
    50 
    51 }
    复制代码

    上面的程序是没有问题的,但不够好!(想起我高中时候数字老师的一句话:我不能说你错,只能说你不对~~~)

    如果是人为来寻找的话,肯定不会再把i移动回第1位,因为主串匹配失败的位置前面除了第一个A之外再也没有A了,我们为什么能知道主串前面只有一个A?因为我们已经知道前面三个字符都是匹配的!(这很重要)。移动过去肯定也是不匹配的!有一个想法,i可以不动,我们只需要移动j即可,如下图:

     

    上面的这种情况还是比较理想的情况,我们最多也就多比较了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”,比较到最后一个才知道不匹配,然后i回溯,这个的效率是显然是最低的。

     

    大牛们是无法忍受“暴力破解”这种低效的手段的,于是他们三个研究出了KMP算法。其思想就如同我们上边所看到的一样:“利用已经部分匹配这个有效信息,保持i指针不回溯,通过修改j指针,让模式串尽量地移动到有效的位置。”

     

    所以,整个KMP的重点就在于当某一个字符与主串不匹配时,我们应该知道j指针要移动到哪

     

    接下来我们自己来发现j的移动规律:

     

    如图:C和D不匹配了,我们要把j移动到哪?显然是第1位。为什么?因为前面有一个A相同啊:

     

    如下图也是一样的情况:

     

    可以把j指针移动到第2位,因为前面有两个字母是一样的:

     

    至此我们可以大概看出一点端倪,当匹配失败时,j要移动的下一个位置k。存在着这样的性质:最前面的k个字符和j之前的最后k个字符是一样的

    如果用数学公式来表示是这样的

    P[0 ~ k-1] == P[j-k ~ j-1]

    这个相当重要,如果觉得不好记的话,可以通过下图来理解:

     

    弄明白了这个就应该可能明白为什么可以直接将j移动到k位置了。

    因为:

    当T[i] != P[j]时

    有T[i-j ~ i-1] == P[0 ~ j-1]

    由P[0 ~ k-1] == P[j-k ~ j-1]

    必然:T[i-k ~ i-1] == P[0 ~ k-1]

    公式很无聊,能看明白就行了,不需要记住。

    这一段只是为了证明我们为什么可以直接将j移动到k而无须再比较前面的k个字符。

     

    好,接下来就是重点了,怎么求这个(这些)k呢?因为在P的每一个位置都可能发生不匹配,也就是说我们要计算每一个位置j对应的k,所以用一个数组next来保存,next[j] = k,表示当T[i] != P[j]时,j指针的下一个位置。

     

    很多教材或博文在这个地方都是讲得比较含糊或是根本就一笔带过,甚至就是贴一段代码上来,为什么是这样求?怎么可以这样求?根本就没有说清楚。而这里恰恰是整个算法最关键的地方。

    复制代码
     1 public static int[] getNext(String ps) {
     2 
     3     char[] p = ps.toCharArray();
     4 
     5     int[] next = new int[p.length];
     6 
     7     next[0] = -1;
     8 
     9     int j = 0;
    10 
    11     int k = -1;
    12 
    13     while (j < p.length - 1) {
    14 
    15        if (k == -1 || p[j] == p[k]) {
    16 
    17            next[++j] = ++k;
    18 
    19        } else {
    20 
    21            k = next[k];
    22 
    23        }
    24 
    25     }
    26 
    27     return next;
    28 
    29 }
    复制代码

    这个版本的求next数组的算法应该是流传最广泛的,代码是很简洁。可是真的很让人摸不到头脑,它这样计算的依据到底是什么?

    好,先把这个放一边,我们自己来推导思路,现在要始终记住一点,next[j]的值(也就是k)表示,当P[j] != T[i]时,j指针的下一步移动位置

    先来看第一个:当j为0时,如果这时候不匹配,怎么办?

     

    像上图这种情况,j已经在最左边了,不可能再移动了,这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。

    如果是当j为1的时候呢?

     

    显然,j指针一定是后移到0位置的。因为它前面也就只有这一个位置了~~~

     

    下面这个是最重要的,请看如下图:

      

     

    请仔细对比这两个图。

    我们发现一个规律:

    当P[k] == P[j]时,

    有next[j+1] == next[j] + 1

    其实这个是可以证明的:

    因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。(next[j] == k)

    这时候现有P[k] == P[j],我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。

    即:P[0 ~ k] == P[j-k ~ j],即next[j+1] == k + 1 == next[j] + 1。

    这里的公式不是很好懂,还是看图会容易理解些。

     

    那如果P[k] != P[j]呢?比如下图所示:

     

    像这种情况,如果你从代码上看应该是这一句:k = next[k];为什么是这样子?你看下面应该就明白了。

     

    现在你应该知道为什么要k = next[k]了吧!像上边的例子,我们已经不可能找到[ A,B,A,B ]这个最长的后缀串了,但我们还是可能找到[ A,B ]、[ B ]这样的前缀串的。所以这个过程像不像在定位[ A,B,A,C ]这个串,当C和主串不一样了(也就是k位置不一样了),那当然是把指针移动到next[k]啦。

     

    有了next数组之后就一切好办了,我们可以动手写KMP算法了:

    复制代码
     1 public static int KMP(String ts, String ps) {
     2 
     3     char[] t = ts.toCharArray();
     4 
     5     char[] p = ps.toCharArray();
     6 
     7     int i = 0; // 主串的位置
     8 
     9     int j = 0; // 模式串的位置
    10 
    11     int[] next = getNext(ps);
    12 
    13     while (i < t.length && j < p.length) {
    14 
    15        if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0
    16 
    17            i++;
    18 
    19            j++;
    20 
    21        } else {
    22 
    23            // i不需要回溯了
    24 
    25            // i = i - j + 1;
    26 
    27            j = next[j]; // j回到指定位置
    28 
    29        }
    30 
    31     }
    32 
    33     if (j == p.length) {
    34 
    35        return i - j;
    36 
    37     } else {
    38 
    39        return -1;
    40 
    41     }
    42 
    43 }
    复制代码

    和暴力破解相比,就改动了4个地方。其中最主要的一点就是,i不需要回溯了。

     

    最后,来看一下上边的算法存在的缺陷。来看第一个例子:

     

    显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]

    所以下一步我们应该是把j移动到第1个元素咯:

     

    不难发现,这一步是完全没有意义的。因为后面的B已经不匹配了,那前面的B也一定是不匹配的,同样的情况其实还发生在第2个元素A上。

    显然,发生问题的原因在于P[j] == P[next[j]]

    所以我们也只需要添加一个判断条件即可:

    复制代码
    public static int[] getNext(String ps) {
    
        char[] p = ps.toCharArray();
    
        int[] next = new int[p.length];
    
        next[0] = -1;
    
        int j = 0;
    
        int k = -1;
    
        while (j < p.length - 1) {
    
           if (k == -1 || p[j] == p[k]) {
    
               if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
    
                  next[j] = next[k];
    
               } else {
    
                  next[j] = k;
    
               }
    
           } else {
    
               k = next[k];
    
           }
    
        }
    
        return next;
    
    } 
    复制代码

    好了,至此。KMP算法也结束了。

    很奇怪,好像不是很难的东西怎么就把我困住这么久呢?

    仔细想想还是因为自己太浮躁了,以前总是草草应付,很多细节都没弄清楚,就以为自己懂了。结果就只能是似懂非懂的。要学东西真的需要静下心来。

    展开全文
  • 本文将以特殊的方式来让人们更好地理解kmp算法,不包括kmp算法的推导,接下来,我们将从朴素算法出发。 在这之前,我们先设主串为S,模式串为T,我们要解决的询问是主串中是否包含模式串(即T是否为S的字串)。 版权...

    本文将以特殊的方式来让人们更好地理解kmp算法,不包括kmp算法的推导,接下来,我们将从朴素算法出发。
    在这之前,我们先设主串为S,模式串为T,我们要解决的询问是主串中是否包含模式串(即T是否为S的子串)。
    版权声明:本文为原创文章,转载请标明出处。

    朴素算法

    朴素算法说白了就是暴力,简单地讲就是先从主串的第一个位置开始逐个对模式串进行匹配,若匹配失败,则从主串的第二个位置继续进行匹配,以此类推,直到匹配成功或主串的结尾。
    举个例子1
    主串S:aabaaced
    模式串T:aac
    首先我们会进行这样的匹配
    aabaaced
    aac
    发现T[0]和S[0]匹配,T[1]和S[1]匹配,而T[2]==c和S[2]==b匹配失败,接着我们会这样
    aabaaced
      aac
    发现T[1]和S[1]匹配,而T[2]==c和S[3]==b匹配失败,接着
    aabaaced
        aac
    发现T[2]和S[2]不匹配,继续
    aabaaced
          aac
    这次终于成功匹配。
    以上所述就是朴素算法,然而我们再来看一个例子
    举个例子2
    主串S:aaaaaaaaaaaaaaaaaaaaab
    模式串T:aaaaab
    如果这个例子我们还用朴素算法去匹配,很显而易见,每次我们都要从头开始匹配,做法如下
    aaaaaaaaaaaaaaaaaaaaab
    aaaaab
    从T[0]到T[5],对S[0]和S[5]依次进行匹配,发现末尾(T[5]和S[5])没有匹配,继续
    aaaaaaaaaaaaaaaaaaaaab
      aaaaab
    从T[0]到T[5],对S[1]和S[6]依次进行匹配,发现末尾(T[5]和S[6])没有匹配,继续
    ……(此处省略大量的中间过程)
    aaaaaaaaaaaaaaaaaaaaab
                                 aaaaab
    终于匹配成功。
    如果用kmp算法,则过程如下:
    aaaaaaaaaaaaaaaaaaaaab
    aaaaab
    从T[0]到T[5],对S[0]和S[5]依次进行匹配,发现末尾(T[5]和S[5])没有匹配,继续
    aaaaaaaaaaaaaaaaaaaaab
      aaaaab
    直接匹配T[5]和S[6]发现匹配失败,继续
    ……(此处省略大量的中间过程)
    aaaaaaaaaaaaaaaaaaaaab
                                      aaaaab
    我们发现kmp算法从第二次匹配开始省略了T[0]到T[4]对S的匹配,因为由kmp算法我们知道T[0]到T[4]一定已经匹配了,不需要再判断,那么kmp算法是怎么知道并利用这些信息的呢,
    接下来我们进入正题。

    kmp算法的理解

    首先我们从朴素算法出发,一步一步去引出kmp算法
    主串S:S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
    模式串T:T[1]T[2]T[3]T[4]T[5]T[6]
    一开始,我们先用朴素算法进行匹配,得到
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
    T[1]T[2]T[3]T[4]T[5]T[6]
    这时候,我们假设前四个匹配成功了,然而S[5]与T[5]匹配失败,即有
    T[1]==S[1]
    T[2]==S[2]
    T[3]==S[3]
    T[4]==S[4]
    T[5]!=S[5]
    按照朴素算法的做法,我们应该把T串往右移,得到这样的式子进行匹配
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
          T[1]T[2]T[3]T[4]T[5]T[6]
    但是这时候我们思考这样一个问题,将模式串右移一位是否有可能成功匹配??
    显而易见,这样匹配成功的充要条件是:
    T[1]==S[2]
    T[2]==S[3]
    T[3]==S[4]
    T[4]==S[5]
    T[5]==S[6]
    T[6]==S[7]
    结合上次匹配的结果,我们可以把这次匹配成功的充要条件进行变化:
    T[1]==S[2]==T[2]
    T[2]==S[3]==T[3]
    T[3]==S[4]==T[4]
    T[4]==S[5]
    T[5]==S[6]
    T[6]==S[7]
    由此我们可以得出一个上次匹配失败后将模式串T右移一位能够匹配成功的充要条件:
    T[1]==T[2]
    T[2]==T[3]
    T[3]==T[4]
    T[4]==S[5]
    T[5]==S[6]
    T[6]==S[7]
    进而得到上次匹配失败后将模式串T右移一位能够过匹配成功的必要条件:
    T[1]==T[2]
    T[2]==T[3]
    T[3]==T[4]
    注意,这个必要条件只和模式串T有关!
    接着我们讨论将模式串右移两位是否能匹配成功:
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
                 T[1]T[2]T[3]T[4]T[5]T[6]
    显而易见,这样匹配成功的充要条件是:
    T[1]==S[3]
    T[2]==S[4]
    T[3]==S[5]
    T[4]==S[6]
    T[5]==S[7]
    T[6]==S[8]
    结合上次匹配的结果,我们可以把这次匹配成功的充要条件进行变化:
    T[1]==S[3]==T[3]
    T[2]==S[4]==T[4]
    T[3]==S[5]
    T[4]==S[6]
    T[5]==S[7]
    T[6]==S[8]
    进而得到上次匹配失败后将模式串T右移两位能够过匹配成功的必要条件:
    T[1]==T[3]
    T[2]==T[4]
    注意,这个必要条件只和模式串T有关!
    最后我们讨论将模式串右移三位是否能匹配成功:
    S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
                       T[1]T[2]T[3]T[4]T[5]T[6]
    显而易见,这样匹配成功的充要条件是:
    T[1]==S[4]
    T[2]==S[5]
    T[3]==S[6]
    T[4]==S[7]
    T[5]==S[8]
    T[6]==S[9]
    结合上次匹配的结果,我们可以把这次匹配成功的充要条件进行变化:
    T[1]==S[4]==T[4]
    T[2]==S[5]
    T[3]==S[6]
    T[4]==S[7]
    T[5]==S[8]
    T[6]==S[9]
    进而得到上次匹配失败后将模式串T右移三位能够过匹配成功的必要条件:
    T[1]==T[4]
    上面讨论了三种情况,在第一次匹配到T[5]的时候匹配失败了,将模式串分别右移动一位,右移动两位,右移动三位
    是否有可能成功
    我们这里设Q为T[1]T[2]T[3]T[4]
    可以发现:
    右移动一位成功的必要条件是T[1]==T[2],T[2]==T[3],T[3]==T[4],即Q的三个前缀等于三个后缀(T[1]T[2]T[3]==T[2]T[3]T[4])

    右移动两位成功的必要条件是T[1]==T[3],T[2]==T[4],即Q的两个前缀等于两个后缀!(T[1]T[2]==T[3]T[4])

    右移动三位成功的必要条件是T[1]==T[4],即Q的一个前缀等于一个后缀!
    注意,这些移动都只和模式串有关!
    这时候,我们可以得出一个结论:
    上面这个例子,T[5]是匹配失败的位置,我们把匹配失败的位置的前面的所有字符看作一个新的串Q,想要知道右移几位有可能匹配成功,我们需要讨论T[5]前面的字符组成的串Q,如果不满足Q的三个前缀等于三个后缀,我们可以直接跳过右移一位的情况,如果不满足Q的两个前缀等于两个后缀,我们可以直接跳过右移两位的情况,等等,而且,如果一旦满足,我们在右移后,不需要从模式串的头部开始匹配,因为如果满足,前面几个就已经匹配好了。就比如上面这个例子,若满足:
    T[1]==T[2]
    T[2]==T[3]
    T[3]==T[4]
    我们可以得到右移一位有可能匹配成功,而且因为有上次匹配失败后留下的信息
    T[2]==S[2]
    T[3]==S[3]
    T[4]==S[4]
    我们可以直接得到
    T[1]==T[2]==S[2]
    T[2]==T[3]==S[3]
    T[3]==T[4]==S[4]
    所以直接匹配T[4]和S[5]即可,这么一来,就是固定主串不动,从匹配失败的位置开始,判断模式串需要右移几位,然后从匹配失败的位置开始匹配即可,上面那个例子就是T[5]与S[5]匹配失败,由T[1]T[2]T[3]==T[2]T[3]T[4]可知接下来需要模式串右移一位并匹配T[4]和S[5]。

    kmp算法的使用

    在实际使用中,我们不可能匹配失败一次就去判断失败字符前面所有字符组成的串的最长相等的前缀和后缀,这样时间复杂度会很高,所以我们需要在匹配之前对模式串进行预处理,对每个字符如果匹配失败,要右移几位进行保存,在匹配中一旦失败,直接跳到那个位置就可以了,我们用next数组进行保存,比如上面的那个例子,T[5]匹配失败了,这时候就要让模式串的指针指向next[5],next[5]是我们在匹配之前就已经预处理过的。
    至于如何处理,本文不给予证明,靠下面的几串代码可以实现,读者自行思考或阅读书籍或其它文章即可。
    获得next数组的代码如下,T为模式串:

    void get_next() {
        next[0] = -1;
        int i = 0, j = -1;
        int len = strlen(T);
        while(i < len) {
            if(j == -1 || T[i] == T[j])
                next[++i] = ++j;
             else
                j = next[j];
        }
    }

    代码很短,其中next[i]代表的是如果在i位置匹配失败,应该从哪个位置继续匹配,跟i前面所有字符组成的串Q的前缀与后缀有关。注意,这个next数组是kmp算法的核心。
    接下来给出匹配的过程代码:

    bool KMP() {
        get_next();
        int len1 = strlen(T);
        int len2 = strlen(S);
        int i = 0, j = 0;           //i指向模式串T,j指向主串S
        while(j < len2) {
            if(T[i] == S[j]) {
                i++;
                j++;
                if(i == len1) {
                    return true;
                }
            } else {
                i = next[i];
                if(i == -1) {
                    j++;i++;
                }
            }
        }
        return false;
    }

    kmp算法的练习建议

    理解kmp算法:poj2752 poj2406 poj1961
    常规kmp算法练习:poj3461 poj2185

    如有错误或不妥之处,欢迎指正~

    展开全文
  • 数据结构+KMP算法

    2019-03-19 10:56:48
    1.KMP算法 next数组从0开始 代码如下: #include&amp;amp;lt;cstdio&amp;amp;gt; #include&amp;amp;lt;cstring&amp;amp;gt; #include&amp;amp;lt;vector&amp;amp;gt; #include&amp;amp;...

    1.KMP算法

    next数组从0开始
    代码如下:

    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<iostream>
    #include<cmath>
    #include<algorithm> 
    using namespace std;
    void getnext(string s,vector<int> &next)
    {
    	next.clear();
    	next.resize(s.size());
    	int i=1,j=0;
    	next[0]=0;
    	for(i=1;i<next.size();i++)
    	{
    		while(s[i]!=s[j]&&j>0)
    		{
    			j=next[j-1];
    		}
    		if(s[i]==s[j])
    		{
    		 j++;	
    		}
    		next[i]=j;	
    	}
    }
    int KMP(string p,string c,vector<int> next)
    {
      int i,j=0;
      for(i=0;i<p.length();i++)
      {
      	while(j>0&&p[i]!=c[j])//先判断不等,再判断相等
      	{
      		j=next[j-1];//j向前回溯,看next值回溯
    	  }
      	if(p[i]==c[j])
      	{
      		j++;
    	  }
    	  }	
    	  if(j==c.length())
    	  
    	  return i-c.length()+1 ;
    	  
    	  else return -1;
    }
    int main()
    {
    string c;
    string p;
    cin>>p;
    cin>>c;
    vector<int> next(10,0);
    getnext(c,next);
    for(int i=0;i<next.size();i++)
    {
    	cout<<next[i]<<" ";
    }
    int y=KMP(p,c,next);
    cout<<y;
    	return 0;
    }
    

    以上代码参照该视频编写
    **

    - 2.邻接矩阵的DFS和BFS

    **

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    typedef struct 
    {
    	int **a;
    	int n;
    	int e;
     } Graph;
     int visit[20]={0};
     void DFS(Graph*G,int n)
     {
     	cout<<n;
     	visit[n]=1;
     	
    	  	for(int i=0;i<G->n;i++)
     	{
     	if(visit[i]!=1&&i!=n&&G->a[n][i]==1)
    	 {
    	 DFS(G,i);
    }
    	 }
     }
     queue<int> q;
    void BFS(Graph*G,int n)
    {
    	int t;
    	cout<<"0";
    	visit[0]=1;
    	q.push(0);
    	while(!q.empty())
    	{
    		t=q.front();
    		q.pop();
    		for(int i=0;i<G->n;i++)
    		{
    		
    		if(G->a[t][i]!=0&&visit[i]!=1&&t!=i)
    		{
    		
    			cout<<i;
    			visit[i]=1;
    			q.push(i);
    		}
    	}
    	}
    }
    int main()
    {
    	int x,y;
    	int i;
    	Graph*G;
    	G=new Graph;
    	G->a=new int*[20];//使用该结构体前必须进行初始化,否则会出现运行错误
    	for(i=0;i<20;i++)
    	{
    		G->a[i]=new int[20];
    	}
    	
    	cout<<"顶点"<<endl; 
    	cin>>G->n;
    	cout<<"边"<<endl; 
        cin>>G->e;
        for(i=0;i<G->n;i++)
    	for(int j=0;j<G->n;j++)
    	{
    		G->a[i][j]=0;
    	}
    
        for(i=0;i<G->e;i++)
        {
        	cin>>x>>y;
        	G->a[x][y]=1;
        	G->a[y][x]=1;
    	}
    	for(i=0;i<G->n;i++)
    	{
    	for(int j=0;j<G->n;j++)
    	{
    		cout<<G->a[i][j];
    	}
    	cout<<endl;
    }
    	//DFS(G,G->n-1);
    	cout<<endl;
    	BFS(G,G->n-1);
    	return 0; 
    }
    
    展开全文
  • 数据结构KMP算法

    2018-10-18 17:39:06
    一. 首先求next值 例如: 模式串 a b a a b c a c  next值 0 1 1 2 2 3 1 2 next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。...
  • 详解KMP算法
  • 串这一节在大一学数据结构时老师并没有着重讲解,只让我们会求一个字符串的next数组就行了,这次学习的时候认真看了下,也花了挺长时间的,好好总结一下: 1、串的匹配是串的基础同时也非常重要的操作,最初人们用...
  • 数据结构KMP算法

    2020-07-10 23:31:16
    数据结构里面的KMP算法,这是在VC6.0里面边写的,上传的是一个工程,可以直接使用的
  • 数据结构--KMP算法

    2018-01-22 11:06:07
    要完善一个String字符串类,那么实现查找子串的功能是必不可少的,实现子串查找可以使用朴素算法,每次匹配一个字符后向右移动一个位置,这样执行下来效率是比较低的,所以就有了KMP算法,它能够准确的知道当前字符...
  • 什么是模式匹配、常见模式匹配算法及C/C++/Java代码 详见...KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KM...
  • KMP算法 如果我们要对下面的主串P和模式串P进行匹配 步骤一:i=3,j=3 模式串 “abab” 对应的 next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当模式串 P 和主串 S 进行匹配时,发现b跟c失配,于是模式...
  • kmp算法是子串配对的一种,并不是速度最快的,但是其算法思想非常巧妙。请允许我尝试用白话描述一下其思想,如果有什么不对的地方,恳请矫正。
  • // KMP字符串模式匹配算法 // 输入: S是主串,T是模式串,pos是S中的起始位置 // 输出: 如果匹配成功返回起始位置,否则返回-1 int KMP(PString S, PString T, int pos) { assert(NULL != S); assert(NULL != T); ...
  • KMP算法数据结构课上讲了两天,还是晕晕乎乎的,先把《算法笔记》里的笔记放上来吧~以后想起来再看 笔记文件过大,出不来可以先等等 笔记很占服务器带宽,访问速度应该挺慢的~ ...
  • 基本数据结构与算法笔记之--KMP算法 注:用于自己复习之用 KMP算法介绍: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称...
  • 1、KMP算法求解什么类型问题? 字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。 2、完整的KMP算法 #include &amp;lt;bits/stdc++.h&amp;gt; ...
  • 数据结构kmp算法

    2019-07-02 00:10:39
    Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名...
  • 代码 #include <iostream> using namespace std; typedef struct { char data[50];//存放串字符 int length;//存放串长 }SqString;//顺序串类型 ...s,char cstr[])//生成串,s为引用型参数 ... int ...
  • KMP算法中虽然计算了nextval的值,但我在此次并没有用到。 课程名称:数据结构 实验项目名称:串基本操作的实现 实验目的: 1.掌握串的模式匹配操作。 实验要求: 1、 分别使用BF和KMP算法完成串的模式...
1 2 3 4 5 ... 20
收藏数 14,304
精华内容 5,721
关键字:

kmp算法数据结构