《数据结构》—— 串的模式匹配算法

一时失言乱红尘 2022-09-12 04:47 170阅读 0赞

### 串的模式匹配 ###

*   *  一、简单的模式匹配算法（BF算法）
     *  二、KMP算法

## 一、简单的模式匹配算法（BF算法） ##

在实际应用中我们常常能用到类似串的模式匹配，也称子串的定位操作。例如单词查找，百度搜索都是串的模式匹配操作。

**字符串模式匹配：** 在主串中找到与模式串相同的⼦串，并返回其所在位置。

*  ⼦串——主串的⼀部分，⼀定存在；
 *  模式串——不⼀定能在主串中找到。

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

**例如：主串为：‘abaabaabcabaa’，模式串：‘baabc’；算出⼦串第⼀个字符的位置。**

【逻辑分析】: 算出主串中有多少个子串， 模式串与子串进行匹配；子串与模式串从第一个开始匹配，当他们的第一个相等，就接着匹配下一个，知道模式串匹配成功或者失败，最后返回结果。  
子串：\{ **abaab,baaba,aabaa,abaab,baabc,aabca,bcaba,cabaa**\}；  
模式串：**baabc** ；

易知：当匹配到第5个子串时，匹配成功，返回子串第一个字符的位置。在循环匹配中，模式串始终是从第一个字符开始匹配；而主串是当子串匹配不成功时+1,再匹配的。

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

在很多场景中，主串远比模式串长得多，即n>>m。  
匹配成功的最好时间复杂度: O(m) ；  
匹配失败的最好时间复杂度: O(n-m+1) = O(n-m)=O(n)；  
匹配失败的最坏时间复杂度：O(n\*m)。

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

int Index(SString S, SString T, int pos)
    {
        
    	//返回模式串T在主串S中第pos个字符之后第S一次出现的位置。若不存在，则返回值为0
    	//其中，T非空，1≤pos≤StrLength(S)
    	int i = pos;
    	int j = 1;
    	while(i<=S.length && j<=T.length)
    	{
        
    		if(S[i]==T[j])
    		{
        
    			++i;
    			++j;
    		} //继续比较后继字符
    		else
    		{
        
    			i=i-j+2;
    			j=1;
    		} //指针后退重新开始匹配
    	}
    	if (j>T.length)
    		return i-T.length;
    	else
    		return 0;
    }

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

**完整代码：**

/***字符串匹配算法***/
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    #define MAXSTRLEN 255   		//用户可在255以内定义最长串长
    typedef char SString[MAXSTRLEN+1];		//0号单元存放串的长度
    
    Status StrAssign(SString T, char *chars) {
         //生成一个其值等于chars的串T
    	int i;
    	if (strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
        
    		T[0] = strlen(chars);	//char长度赋给T[0]
    		for (i = 1; i <= T[0]; i++)
    			T[i] = *(chars + i - 1);  //char的值赋给字符串T
    		return OK;
    	}
    }
    
    //算法4.1　BF算法
    int Index(SString S, SString T, int pos)
    {
        
    	//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0
    	//其中，T非空，1≤pos≤StrLength(S)
    	int i = pos;
    	int j = 1;
    	while(i <= S[0]&&j <= T[0])
    	{
        
    		if(S[i]==T[j])
    		{
        
    			++i;
    			++j;
    		} //继续比较后继字符
    		else
    		{
        
    			i=i-j+2;
    			j=1;
    		} //指针后退重新开始匹配
    	}
    	if (j > T[0])
    		return i - T[0];
    	else
    		return 0;
    	return 0;
    }//Index
    
    int main()
    {
        
    	SString S;	//S串为主串
    	StrAssign(S,"abaabaabcabaa") ;
    	SString T;	//T串为模式串；
    	StrAssign(T,"baabc") ;
    	cout<<"主串和子串在第"<<Index(S,T,1)<<"个字符处首次匹配\n";
    	return 0;
    }

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

## 二、KMP算法 ##

上面的BF算法中频繁的重复比较相当于模式串在不断地进行自我比较，导致其效率低下。我们不得不思考有没有更高校的方法。

我们不想要主串回溯操作，利用部分匹配直接跳转到还没进行匹配的字符那里。

next数组: 当模式串的第j个字符匹配失败时，令模式串跳到next\[j\]再继续匹配。

当子串和模式串不匹配时，主串指针i不回溯，模式串指针j=next\[j\]。

KMP算法，最坏时间复杂度 O(m+n)；其中，求 next 数组时间复杂度 O(m)，模式匹配过程最坏时间复杂度 O(n)。

/***字符串匹配算法***/
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    #define MAXSTRLEN 255 	//用户可在255以内定义最长串长
    typedef char SString[MAXSTRLEN+1]; //0号单元存放串的长度
    
    Status StrAssign(SString T, char *chars) {
         //生成一个其值等于chars的串T
    	int i;
    	if (strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
        
    		T[0] = strlen(chars);
    		for (i = 1; i <= T[0]; i++)
    			T[i] = *(chars + i - 1);
    		return OK;
    	}
    }
    //计算next函数值
    void get_next(SString T, int next[])
    {
         //求模式串T的next函数值并存入数组next
    	int i = 1, j = 0;
    	next[1] = 0;
    	while (i < T[0])
    		if (j == 0 || T[i] == T[j]) 
    		//根据模式串T，求出next数组
    		{
        
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    			j = next[j];
    }//get_next
    
    //KMP算法
    int Index_KMP(SString S, SString T, int pos, int next[])
    {
         	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
    	//其中，T非空，1≤pos≤StrLength(S)
    	int i = pos, j = 1;
    	while (i <= S[0] && j <= T[0])
    		if (j == 0 || S[i] == T[j]) // 继续比较后继字
    		{
        
    			++i;
    			++j;
    		}
    		else //利⽤next数组进⾏匹配（主串指针不回溯）
    			j = next[j]; // 模式串向右移动
    	if (j > T[0]) // 匹配成功
    		return i - T[0];
    	else
    		return 0;
    }
    
    int main()
    {
        
    	SString S;
    	StrAssign(S,"aaabbaba") ;
    	SString T;
    	StrAssign(T,"abb") ;
    	int *p = new int[T[0]+1]; // 生成T的next数组
    	get_next(T,p);
    	cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
    	return 0;
    }

[d22766dc21704eb48463a307444969fb.png]: /images/20220828/c2162cdd5be44f27a6003fc45a38be02.png