字符串的模式匹配

目录

1.模式匹配

（1）朴素模式的匹配方法

（2）KMP算法

（3）KMP优化方法

---

1.模式匹配

在主串中找到与模式串相同的子串，并返回子串的位置。模式匹配在串处理系统中是最重要的操作之一。

（1）朴素模式的匹配方法

 主串的长度为m,子串的长度为n：将主串中所有长度为m的子串依次与模式串进行比较，直到找到一个完全匹配的子串或者所有的子串都不匹配为止，最多比较的次数为（m-n+1）。

主串：qinghuadaxuecomputervisionmydream

子串：vision

#include
#include
#include
 
#define maxn 100
 
char S[maxn];
char T[maxn];
 
 
void substr(char *s,char r[maxn],int i,int n){
	int k=0;
	for(int j=i;j<(n+i);j++){
		r[k]=s[j];
		k++;
	}
	r[k]='\0';
}
 
//比较串是否相同
bool Compare(char*s,char*t){
	int n=strlen(s);
	int m=strlen(t);
	for(int i=0;i
		if(s[i]!=t[i]){
			return false;
		}
	}
	return true;
} 
 
 
//方法一 
int index_1(char*s,char*t,int m,int n){
	int pos=0;
	int len=m-n+1;
	while(pos<=len){
		char r[maxn];
		substr(s,r,pos,n);
		if(!Compare(r,t)){
			pos++;
		}else{
			return pos;
		}
	}
	return -1;
}
//方法二
int index_2(char*s,char*t,int m,int n){
	int pos=0;
	int j=0,i=0;
	while(i
		if(s[i]==t[j]){
			i++;
			j++;
		}else{
			i=i-j+1;
			j=0;
		}
	}
	if(j>=n){
		return i-n;
	}else{
		return -1;
	}
}
 
 
int main(){
	printf("请输入主串: ");
	scanf("%s",&S);
	printf("\n");
	printf("请输入模式串: ");
	scanf("%s",&T);
	int m=strlen(S);
	int n=strlen(T);
	int pos=index_2(S,T,m,n);
	if(pos==-1){
		printf("匹配失败!\n");
	}else{
		printf("匹配成功!\n");
		printf("pos = %d\n",pos);
	}
	return 0;
}

注：上面的程序每个子串都要进行比较m个字符，共n-m+1个子串，因此上面的时间复杂度最坏的情况下O(（n-m+1）*m)≈O(n*m)（主串n＞＞模式串m）.因此对其进行改进的算法KMP。

（2）KMP算法

KMP算法是由D.E.Knuth，V.R.Pratt和J.H.Morris同时发现的，简称KMP算法。KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

思想：每当一趟匹配过程中出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一段距离之后，继续进行比较。

怎么实现指针i不需要回溯呢？也就是当主串中第i个字符与模式中第j个字符“失配”时，主串中第i个字符（指针i不回溯）应与模式中哪个字符再比较？

 

 

void get_next(char*t,int next[maxn],int n){
	int i=0;
	int j=-1;
	next[i]=-1;
	while(i
		if(j==-1||t[i]==t[j]){
			i++;
			j++;
			next[i]=j;
		}else{
			j=next[j];
		}
	}
}

 

#include
#include
#include
 
#define maxn 100
 
char S[maxn];
char T[maxn];
 
void get_next(char*t,int next[maxn],int n){
	int i=0;
	int j=-1;
	next[i]=-1;
	while(i
		if(j==-1||t[i]==t[j]){
			i++;
			j++;
			next[i]=j;
		}else{
			j=next[j];
		}
	}
}
int index(char*s,char*t,int next[maxn],int m,int n){
	int pos=0;
	int j=0,i=0;
	while(i
		if(j==-1||s[i]==t[j]){
			i++;
			j++;
		}else{
			j=next[j];
		}
	}
	if(j>=n){
		return i-n;
	}else{
		return -1;
	}
}
 
 
int main(){
	int next[maxn];
	for(int i=0;i
		next[i]=0;
	}
	printf("请输入主串: ");
	scanf("%s",&S);
	printf("\n");
	printf("请输入模式串: ");
	scanf("%s",&T);
	int m=strlen(S);
	int n=strlen(T);
	//得到next函数 
	get_next(T,next,n);
	//abaabac=>0 1 1 1 2 3 1
	printf("next = ");
	for(int i=0;i
		printf("%d\t",next[i]); 
	}
	printf("\n");
	//匹配位置 
	int pos=index(S,T,next,m,n);
	if(pos==-1){
		printf("匹配失败!\n");
	}else{
		printf("匹配成功!\n");
		printf("pos = %d\n",pos);
	}
	return 0;
}

 注：时间复杂度为O(n+m).

（3）KMP优化方法

方法一：首先求解出next函数值，然后根据函数值求解nextval函数值：

//这里的char*t存储的字符是从1开始的 
void Get_nextval(char*t,int next,int nextval,int n){
	nextval[1]=0;
	for(int j=2;j<=n;j++){
		if(t[next[j]]==t[j]){
			nextval[j]=nextval[next[j]];
		}else{
			nextval[j]=next[j];
		}
	}
}

方法二：直接使用下面的方法求解nextval函数值也可以

void get_next(char*t,int next[maxn],int n){
	int i=0;
	int j=-1;
	nextval[i]=-1;
	while(i
		if(j==-1||t[i]==t[j]){
			i++;
			j++;
			if(t[i]!=t[j]){
				nextval[i]=j;
			}else{
				nextval[i]=nextval[j];
			}
		}else{
			j=next[j];
		}
	}
}