快捷搜索: 王者荣耀 脱发

详细解说kmp,第五届蓝桥杯决赛第三题

题目就是补全代码. 此处主要简单证明且叙述kmp原理.

prefix[j] 存放当模式串匹配到j,位置与主串位置i,存在s[i]!=p[j]时,进行性下次操作 只需要使得下次j=prefix[j],在与i,进行匹配. 因此prefix[i]数组中存放这样的整数k 使得有模式串 p[1 to k-1] 与 p[(i-1)-(k-1)+1 to (i-1)] 完全匹配时的k 如最上面图中的prefix[7]=4; 因为p[1 to 3] 与 p[(7-1)-(4-1)+1 to (7-1)] (即p[4 to 6])完全相等 因此prefix[7]=4, 下次j=7;失败时依据上图原理j=prefix[j],在进行s[7] 与 p[4]的匹配即可. 换句话说prefix[j]中存放的是p j-1的后缀串 与p j-1的前缀串最大匹配串长 此处定义 串s ,不是s自身的子串,因此根不能为自己的前缀串或后缀串 prefix[] 数组的求法可以用朴素的方法来求 int pn,int i,int k; for(i=1;i for(k=1;k 如果p[1 to k] 与 p[k to pn]相等时 if(ismatch(p,1,k,p,k,pn))) prefix[i]=max(prefix[i],k); } } 或者根据如下事实写出代码 如果已经有 p[1 to k] 与 p[i-k+1 to i] 相等 此时如果 p[k+1]等于p[i+1] 时prefix[i+2]=k+1; 并且i++,j++;进行下次比较,仍存在p[1 to k] 与 p[i-k+1 to i+1]相等.//有归纳法可得。 如果不相等 另j=prefix[j],prefix[j]的意义, 则存在 p[1 to prefix[j]] 等于 p[(j-1) - prefix[j] +1 to (j-1)]相等非常重要 因此另j=prefix[j];进行下次比较. 到此为止kmp思路就说明完毕了 下面是代码(参照数据结构)

#include <cstring>
#include <iostream>
using namespace std;
int prefix[100]={0};
int Prefix(char p[]){
	int i,j=0;
	prefix[i=1]=0;
	while(i<p[0]){
		if(j==0||p[i]==p[j]){
			i++;
			j++;
			prefix[i]=j;
		}else
		      j=prefix[j];
	}
}
int Kmp(char s[100],int pos,char p[100]){
	int i=pos;
	int j=1;
	Prefix(p);
	while(i<=s[0]&&j<=p[0]){
		if(j==0||s[i]==p[j]){
			i++;
			j++;
		}else{
			j=prefix[j];
		}
	}
	if(j>p[0])
	      return i-p[0];
	return -1;
}
int main(){
	char s[100];
	char p[100];
	cin>> s+1 >> p+1 ;
	s[0]=strlen(s+1);
	p[0]=strlen(p+1);
	cout<< Kmp(s,1,p)<<endl;
	return 0;
}
题目就是补全代码. 此处主要简单证明且叙述kmp原理. prefix[j] 存放当模式串匹配到j,位置与主串位置i,存在s[i]!=p[j]时,进行性下次操作 只需要使得下次j=prefix[j],在与i,进行匹配. 因此prefix[i]数组中存放这样的整数k 使得有模式串 p[1 to k-1] 与 p[(i-1)-(k-1)+1 to (i-1)] 完全匹配时的k 如最上面图中的prefix[7]=4; 因为p[1 to 3] 与 p[(7-1)-(4-1)+1 to (7-1)] (即p[4 to 6])完全相等 因此prefix[7]=4, 下次j=7;失败时依据上图原理j=prefix[j],在进行s[7] 与 p[4]的匹配即可. 换句话说prefix[j]中存放的是p j-1的后缀串 与p j-1的前缀串最大匹配串长 此处定义 串s ,不是s自身的子串,因此根不能为自己的前缀串或后缀串 prefix[] 数组的求法可以用朴素的方法来求 int pn,int i,int k; for(i=1;i for(k=1;k 如果p[1 to k] 与 p[k to pn]相等时 if(ismatch(p,1,k,p,k,pn))) prefix[i]=max(prefix[i],k); } } 或者根据如下事实写出代码 如果已经有 p[1 to k] 与 p[i-k+1 to i] 相等 此时如果 p[k+1]等于p[i+1] 时prefix[i+2]=k+1; 并且i++,j++;进行下次比较,仍存在p[1 to k] 与 p[i-k+1 to i+1]相等.//有归纳法可得。 如果不相等 另j=prefix[j],prefix[j]的意义, 则存在 p[1 to prefix[j]] 等于 p[(j-1) - prefix[j] +1 to (j-1)]相等非常重要 因此另j=prefix[j];进行下次比较. 到此为止kmp思路就说明完毕了 下面是代码(参照数据结构) #include #include using namespace std; int prefix[100]={0}; int Prefix(char p[]){ int i,j=0; prefix[i=1]=0; while(i p[0]) return i-p[0]; return -1; } int main(){ char s[100]; char p[100]; cin>> s+1 >> p+1 ; s[0]=strlen(s+1); p[0]=strlen(p+1); cout<< Kmp(s,1,p)<
经验分享 程序员 微信小程序 职场和发展