118-串匹配的KMP算法的实现

偏执的太偏执、 2022-12-30 15:49 115阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h> 
    #include<assert.h>
    
    void GetNext(const char *p, int *next)//获取k的值 
    {
        
    	next[0] = -1;
    	next[1] = 0;
    	int lenp = strlen(p);
    	int i = 1;
    	int k = 0;
    	while (i + 1 < lenp)
    	{
        
    		if (k == -1 || p[i] == p[k])
    		{
        
    			next[++i] = ++k;
    			/*
    			next[i + 1] = k + 1;
    			i++;
    			k++;
    			*/
    		}
    		else
    		{
        
    			k = next[k];
    			/*
    			if (k == -1)
    			{
    				next[i + 1] = k+1;
    				i++;
    				k++;
    			}
    			*/
    		}
    	}
    }
    
    // 时间复杂度O(n+m)   空间复杂度O(m)
    int KMP(const char *s, const char *p, int pos)//KMP算法的实现 
    {
        
    	int lens = strlen(s);
    	int lenp = strlen(p);
    	if (s == NULL || p == NULL || lenp > lens)  return -1;
    	int i = pos;
    	int j = 0;
    	int *next = (int *)malloc(sizeof(int) * lenp);
    	assert(next != NULL);
    	GetNext(p, next);
    	while (i < lens && j < lenp)
    	{
        
    		if (j == -1 || s[i] == p[j])
    		{
        
    			i++;
    			j++;
    		}
    		else
    		{
        
    			j = next[j];
    			/*
    			if (j == -1)
    			{
    				i++;
    				j++;
    			}
    			*/
    		}
    	}
    	free(next);
    	if (j == lenp)
    	{
        
    		return i - j;
    	}
    
    	return -1;
    }
    
    int main()
    {
        
    	const char *s = "ababcabcdabcde";
    	const char *p = "abcd";
    
    	printf("%d\n", KMP(s, p, 6));
    	return 0;
    }

**运行结果如下**  
![在这里插入图片描述][20201226170514545.png_pic_center]  
**BF方法**  
从主串s 和子串t 的第一个字符开始，将两字符串的字符一一比对，如果出现某个字符不匹配，主串回溯到第二个字符，子串回溯到第一个字符再进行一一比对。如果出现某个字符不匹配，主串回溯到第三个字符，子串回溯到第一个字符再进行一一比对…一直到子串字符全部匹配成功。  
**竖直线表示相等，闪电线表示不等**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
这种算法在最好情况下时间复杂度为O(n)。即子串的n个字符正好等于主串的前n个字符，而最坏的情况下时间复杂度为O(m\*n)。相比而言这种算法空间复杂度为O(1)，即不消耗空间而消耗时间。

**KMP的主要思想是：“空间换时间”**  
提出一个概念：一个字符串最长相等前缀和后缀。  
字符串 abcdab  
前缀的集合：\{a,ab,abc,abcd,abcda\}  
后缀的集合：\{b,ab,dab,cdab,bcdab\}  
那么最长相等前后缀就是ab  
**做个小练习：**  
字符串：abcabfabcab中最长相等前后缀是什么呢：  
是abcab

## 图解KMP ##

第一个长条代表主串，第二个长条代表子串。红色部分代表两串中已匹配的部分，绿色和蓝色部分分别代表主串和子串中不匹配的字符。  
再具体一些：这个图代表主串"abcabeabcabcmn"和子串"abcabcmn"。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
现在发现了不匹配的地方，根据KMP的思想我们要将子串向后移动，现在解决要移动多少的问题。之前提到的最长相等前后缀的概念有用处了。因为红色部分也会有最长相等前后缀。如下图：  
![在这里插入图片描述][20201228220255274.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
灰色部分就是红色部分字符串的最长相等前后缀，我们子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个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；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
也是不匹配的字符处的next数组next\[5\]应该保存的值，也是子串回溯后应该对应的字符的下标。 所以？=next\[5\]=2。接下来就是比对是s\[5\]和t\[next\[5\]\]的字符。这里也是最奇妙的地方，也是为什么KMP算法的代码可以那么简洁优雅的关键。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]  
KMP算法中多了一个求数组的过程，多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m)，因后面匹配中主串不回溯，比较次数可记为n，所以KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m\*n)，KMP算法提速是非常大的，这一点点空间消耗换得极高的时间提速是非常有意义的，这种思想也是很重要的。

**解释next数组构造过程中的回溯问题**  
下面的长条代表子串，红色部分代表当前匹配上的最长相等前后缀，蓝色部分代表t.data\[j\]。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]

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);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/86d37d75c85d454e9461d529360763e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201226170441757.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20201226170514545.png_pic_center]: https://img-blog.csdnimg.cn/20201226170514545.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201228215838209.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201228215844637.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201228220148945.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20201228220255274.png_pic_center]: https://img-blog.csdnimg.cn/20201228220255274.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201228220300845.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201228220337207.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/202012282204523.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201228220546657.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201228220733194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201228220738460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20201228220824186.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center