poj3461 (KMP&&扩展KMP)

2017年05月21日 10点热度 0人点赞 0条评论

题目大意是求串w在串t中出现的次数,例如aa在aaa中出现了两次.

Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0

//t是主串,w是模式串
//kmp算法 
#include
#include
#include
using namespace std;
const int mw=10100,mt=1000100;
char w[mw],t[mt];
int next[mw];
void getnext(){
	int j=-1,i=0,len=strlen(w);
	next[0]=-1;
	while(i0&&w[j]!=t[i]) j=next[j];
		if(w[j]==t[i]) ++j;
		if(j==lenw){
			cnt++;
			j=next[j];
		}
	}
	return cnt;
}
int main(){
	int n;
	scanf("%d",&n);
	while(n>0){
		n--;
		scanf("%s%s",w,t);
		printf("%dn",kmp());
	}
	return 0;
}

上面那个代码又bug,但是在poj上过了

//t是主串,w是模式串 
//扩展kmp算法,就多了两行代码 
#include
#include
#include
using namespace std;
const int mw=10100,mt=1000100;
char w[mw],t[mt];
int nextval[mw];
void getnext(){
	int j=-1,i=0,len=strlen(w);
	nextval[0]=-1;
	while(i0){
		n--;
		scanf("%s%s",w,t);
		printf("%dn",kmp());
	}
	return 0;
}

一般的kmp算法在某些情况下有缺陷,例如模式aaaab在和主串

aaabaaaab匹配时,当i=4、j=4时s.ch[4]!=t.ch[4],那么一般的next数组就要多进行几次比较。

但是在本题中好像没有故意去卡扩展KMP,用了扩展KMP耗时反而长了。

poj的数据好水啊。

未经允许不得转载!poj3461 (KMP&&扩展KMP)

update

纸上得来终觉浅, 绝知此事须躬行。