串的模式匹配算法设计（数据结构学习笔记）

谁借莪１个温暖的怀抱￠ 2022-12-28 04:20 85阅读 0赞

### 文章目录 ###

*  BF算法、KMP算法
 *   *  BF算法
     *   *  算法过程
         *  算法代码
         *   *  串的定义
             *  算法设计
             *  完整代码
         *  算法总结
     *  KMP算法
     *   *  算法过程
         *  next数组
         *   *  next数组的公式
             *  next数组程序代码
         *  算法代码
         *   *  串的定义
             *  算法设计
             *  完整代码
         *  算法总结
     *  改进的KMP算法
     *   *  nextval数组
         *   *  nextval数组公式
         *  算法代码
         *   *  算法设计
         *  算法总结

--------------------

# BF算法、KMP算法 #

串的模式匹配问题就是在串s中找到一个与串t相等的子串，通常将串s称为**目标串**，串t称为**模式串**，因此该问题被称为**模式匹配问题**。  
Brute-Force算法与Knuth-Morris-Pratt算法都是解决串的模式匹配问题的算法设计，但二者效率不同，使用场景也不尽相同。

## BF算法 ##

BF算法就是暴力的子串匹配算法，也称简单匹配算法，通过不断遍历目标串以及模式串来进行串的模式匹配，即使用穷举的思路。

### 算法过程 ###

> 运用两个变量i,j来分别遍历目标串s(“aaaaab”)和模式串t(“aaab”)。  
> 1、i=0,j=0时，第一次遍历发现匹配失败，变量i回溯(i=i-j+1=1)，变量j从头开始(j=0)。

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

> 2、 i=1,j=0时，第二次遍历发现匹配失败，变量i回溯并向前移动一位(i=i-j+1=2)，变量j从头开始(j=0)。

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

> 3、 i=2,j=0时，第三次遍历发现匹配成功，此时j以及越界（或者认为j等于模式串的长度），返回i-t.length=2为串的匹配位置

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

### 算法代码 ###

#### 串的定义 ####

typedef struct
    {
        
    	char data[10000];
    	int length;
    }SqString;

#### 算法设计 ####

int BF(SqString s,SqString t)
    {
        
    	int i=0,j=0;
    	
    	while(i<s.length&&j<t.length){
        
    		if(s.data[i]==t.data[j])
    			i++,j++;	//当前两字符匹配，则i,j向后移动一位 
    		else	//当前两字符不匹配时，i回溯，j为0 
    			i=i-j+1,j=0;
    	}
    	if(j>=t.length)	//若j的值大于等于模式串的长度则证明匹配成功 
    		return (i-t.length);	//返回从何处串匹配成功 
    	else
    		return -1;	//无法匹配返回-1 
    }

#### 完整代码 ####

#include <stdio.h>
    
    typedef struct
    {
        
    	char data[10000];
    	int length;
    }SqString;
    
    //生成串函数 
    void StrAssign(SqString &k,char a[])
    {
        
    	int i;
    	for(i=0;a[i]!='\0';i++)
    		k.data[i]=a[i];
    	k.data[i]='\0';
    	k.length=i;
    }
    
    //BF算法 
    int BF(SqString s,SqString t)
    {
        
    	int i=0,j=0;
    	
    	while(i<s.length&&j<t.length){
        
    		if(s.data[i]==t.data[j])
    			i++,j++;	//当前两字符匹配，则i,j向后移动一位 
    		else	//当前两字符不匹配时，i回溯，j为0 
    			i=i-j+1,j=0;
    	}
    	if(j>=t.length)	//若j的值大于等于模式串的长度则证明匹配成功 
    		return (i-t.length);	//返回从何处串匹配成功 
    	else
    		return -1;	//无法匹配返回-1 
    }
    
    int main()
    {
        
    	char a[10000],b[10000];
    	SqString s,t;
    	
    	gets(a);
    	gets(b);
    	
    	StrAssign(s,a);
    	StrAssign(t,b);
    	
    	printf("%d",BF(s,t));
    	
    	return 0;
    }

### 算法总结 ###

*  `不难发现BF算法在最好的情况下时间复杂度为O(m)，最坏的情况下算法复杂度为O(m*n)，BF算法的平均时间复杂度为O(m*n)`

## KMP算法 ##

KMP算法利用部分匹配信息来避免BF算法中主串指针多余的回溯过程，从而使得算法效率得到了提高。

### 算法过程 ###

以目标串(“aaaaab”)与模式串(“aaab”)为例

> 1、首先与BF算法一样，目标串和模式串进行遍历比较匹配，当匹配到s\[3\],t\[3\]时发现s\[3\]!=t\[3\]。

![在这里插入图片描述][20201214164224356.png]

> 2、但在此次匹配的过程中我们发现已经有了部分匹配信息可以利用，串s\[0\]s\[1\]s\[2\]=t\[0\]t\[1\]t\[2\]，那么就存在一个数k< j 时s\[0\]…s\[k\]=t\[0\]…t\[k\]。

![在这里插入图片描述][20201214164228860.png]

> 3、我们在模式串t中发现在j=3,t\[3\]前存在最多长度为2的前缀串与后缀串相等，即t\[0\]t\[1\]=t\[1\]t\[2\]，而我们又知道s\[1\]s\[2\]=t\[1\]t\[2\]，因此可以得知**t\[0\]t\[1\]=s\[1\]s\[2\]**。

![在这里插入图片描述][20201214164236965.png]

> 4、通过这个信息我们就可以将模式串t向左滑动1个单位(j-next\[j\])，亦即i=3不变，j=2，用s\[3\]与t\[2\]进行比较。（next数组后面再解释）

![在这里插入图片描述][20201214164241293.png]

### next数组 ###

next数组中存放的为模式串中t\[j\]前存在的前缀串与后缀串相等的最大长度。

#### next数组的公式 ####

> （一）默认t\[0\]的next数组的值为-1，当用到-1时就意味着无部分匹配信息可用，那么就需要像BF算法一样i++,j=0，而算法中为了统一使用i++,j++来达到这个目的，故将j=-1。  
> （二）实际上next数组的求解过程，就是模式串自身的匹配过程，例如模式串(“abababca”)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]

![9][]

![10][]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 7]

#### next数组程序代码 ####

void GetNext(SqString t,int next[])
    {
        
    	int i=0,j=-1;
    	next[0]=-1;
    	
    	//这个过程实际上是间接利用KMP算法对模式串t进行的匹配 
    	while(i<t.length){
        
    		if(j==-1||t.data[i]==t.data[j]){
        	//j=-1意味着串t将从头开始比较 
    			i++,j++;	//指向串t的指针向后移一位 
    			next[i]=j;	//这一步是next算法特有的 
    		}
    		else
    			j=next[j];	//利用部分匹配信息跳过多余回溯 
    	}
    }

### 算法代码 ###

#### 串的定义 ####

typedef struct
    {
        
    	char data[10000];
    	int length;
    }SqString;

#### 算法设计 ####

int KMP(SqString s,SqString t)
    {
        
    	int i=0,j=0;
    	int next[10000];
    	GetNext(t,next);
    	while(i<s.length&&j<t.length){
        
    		if(j==-1||s.data[i]==t.data[j])	//j=-1意味着模式串t将从头开始比较 
    			i++,j++; //指向串s与串t的指针同时向后移动一位 
    		else
    			j=next[j];	//利用部分匹配信息跳过多余回溯 
    	}
    	if(j>=t.length)	//若j的值大于等于模式串的长度则证明匹配成功 
    		return (i-t.length);	//返回从何处串匹配成功 
    	else
    		return -1;	//无法匹配返回-1 
    }

#### 完整代码 ####

#include <stdio.h>
    
    typedef struct
    {
        
    	char data[10000];
    	int length;
    }SqString;
    
    //生成串函数 
    void StrAssign(SqString &k,char a[])
    {
        
    	int i;
    	for(i=0;a[i]!='\0';i++)
    		k.data[i]=a[i];
    	k.data[i]='\0';
    	k.length=i;
    }
    
    //求next数组函数 
    void GetNext(SqString t,int next[])
    {
        
    	int i=0,j=-1;
    	next[0]=-1;
    	
    	//这个过程实际上是间接利用KMP算法对模式串t进行的匹配 
    	while(i<t.length){
        
    		if(j==-1||t.data[i]==t.data[j]){
        	//j=-1意味着串t将从头开始比较
    			i++,j++;	//指向串t的指针向后移一位 
    			next[i]=j;	//这一步是next算法特有的 
    		}
    		else
    			j=next[j];	//利用部分匹配信息跳过多余回溯 
    	}
    }
    
    //KMP算法 
    int KMP(SqString s,SqString t)
    {
        
    	int i=0,j=0;
    	int next[10000];
    	GetNext(t,next);
    	while(i<s.length&&j<t.length){
        
    		if(j==-1||s.data[i]==t.data[j])	//j=-1意味着模式串t将从头开始比较 
    			i++,j++; //指向串s与串t的指针同时向后移动一位 
    		else
    			j=next[j];	//利用部分匹配信息跳过多余回溯 
    	}
    	if(j>=t.length)	//若j的值大于等于模式串的长度则证明匹配成功 
    		return (i-t.length);	//返回从何处串匹配成功 
    	else
    		return -1;	//无法匹配返回-1 
    }
    
    int main()
    {
        
    	char a[10000],b[10000];
    	SqString s,t;
    	
    	gets(a);
    	gets(b);
    	
    	StrAssign(s,a);
    	StrAssign(t,b);
    	
    	printf("%d",KMP(s,t));
    	
    	return 0;
    }

### 算法总结 ###

KMP算法中求next数组的时间复杂度为O(m)，KMP算法的平均时间复杂度为O(m+n)，是要优于BF算法的，但并非所有时候KMP算法都优于BF算法，`当模式串的next数组中next[0]=-1，而其他元素值均为0时，KMP算法退化为BF算法`。**KMP算法中的next数组仍然存在缺陷。**

## 改进的KMP算法 ##

以目标串s(“aaabaaaab”)与模式串t(“aaaab”)为例  
首先求出next数组  
![在这里插入图片描述][20201214164819217.png]

> 第一次匹配发现匹配失败

![在这里插入图片描述][20201214164728219.png]

> 这时会发现模式串t中前4个字符都相同且都为a，也就是说无论利用next数组如何回溯都会匹配失败

![在这里插入图片描述][20201214164725760.png]

![在这里插入图片描述][20201214164654436.png]

![在这里插入图片描述][20201214164640751.png]

![在这里插入图片描述][20201214164631203.png]

> 直到j=-1，模式串t从头开始与目标串s进行匹配时，才匹配成功

![在这里插入图片描述][20201214164616317.png]

**由此可见原KMP算法中next数组中存在着多余的匹配过程。也就是当当前字符与回溯字符相同时就可跳过这次回溯过程直到遇到不同字符为止**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 8]

那么我们就改进next数组为nextval数组

### nextval数组 ###

![在这里插入图片描述][2020121416460667.png]

#### nextval数组公式 ####

> （一）默认取nextval\[0\]=-1。  
> （二）如果在j=1处“失配”，那么将跳转到t\[next\[j\]\]=t\[0\]处，但可见t\[0\]=t\[1\]，因此我们可以推出，如果t\[j\]=t\[next\[j\]\]，那么nextval\[j\]=nextval\[next\[j\]\]。同理，j=1,j=2,j=3时nextval值都为-1。如果t\[j\]!=t\[next\[j\]\]时，nextval\[j\]=next\[j\]

*  nextval\[0\]=-1
 *  当t\[j\]=t\[next\[j\]\]时： nextval\[j\]=nextval\[next\[j\]\]
 *  否则： nextval\[j\]=next\[j\]

整个nextval数组的初始化为：  
![在这里插入图片描述][20201214164546311.png]

### 算法代码 ###

#### 算法设计 ####

void GetNextval(SqString t,int nextval[])
    {
        
    	int i=0,j=-1;
    	nextval[0]=-1;	//默认nextval[0]为-1
    	while(j<t.length){
        
    		if(j==-1||t.data[i]==t.data[j]){
        	
    			i++,j++;
    			if(t.data[i]!=t.data[j])	//当t[i]!=t[next[j]]时
    				nextval[i]=j;	//nextval[j]=next[j]
    			else
    				nextval[i]=nextval[j];	//当t[i]==t[next[j]]时,nextval[j]=nextval[next[j]] 
    		}
    		else
    			j=nextval[j];
    	}
    }

### 算法总结 ###

改进后的KMP算法时间复杂度也是O(m+n)

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/1e480d91a6a143688add7eca98bb22f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/e0ec84f332d44983a836fdecc6d7f759.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: /images/20221120/36ae4a7503274af08d6c8b0250cdad76.png
[20201214164224356.png]: /images/20221120/a063c92e575a46f3be80125bc80b9387.png
[20201214164228860.png]: /images/20221120/71f8bd1d147a43dc8b76f472c645e206.png
[20201214164236965.png]: /images/20221120/0ecd7671897b41408877eb3ebe197f27.png
[20201214164241293.png]: /images/20221120/059f2a08f1fb47978f723c3989074c7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]: /images/20221120/3cc6daf8cd204652a7f16177b83d5a64.png
[9]: https://img-blog.csdnimg.cn/20201214164251648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[10]: https://img-blog.csdnimg.cn/20201214164259455.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201214164304717.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201214164309383.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201214164314772.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201214164319476.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[20201214164819217.png]: https://img-blog.csdnimg.cn/20201214164819217.png
[20201214164728219.png]: https://img-blog.csdnimg.cn/20201214164728219.png
[20201214164725760.png]: https://img-blog.csdnimg.cn/20201214164725760.png
[20201214164654436.png]: https://img-blog.csdnimg.cn/20201214164654436.png
[20201214164640751.png]: https://img-blog.csdnimg.cn/20201214164640751.png
[20201214164631203.png]: https://img-blog.csdnimg.cn/20201214164631203.png
[20201214164616317.png]: https://img-blog.csdnimg.cn/20201214164616317.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201214164612172.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[2020121416460667.png]: https://img-blog.csdnimg.cn/2020121416460667.png
[20201214164546311.png]: https://img-blog.csdnimg.cn/20201214164546311.png