社区讨论

样例过了,但是测试点WA???

P8835 [传智杯 #3 决赛] 子串参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo0yps3b
此快照首次捕获于
2023/10/22 12:22
2 年前
此快照最后确认于
2023/11/02 11:56
2 年前
查看原帖
CPP
#include<stdio.h>
#include<string.h>
#define MAXSIZE 1005
int next[MAXSIZE];

void init_next(char* m,int len_m){
	next[0]=-1;
	next[1]=0;
	int i=2,j;
	
	while(i<len_m){
		if(j=-1){
			next[i++]=0;
			j=i-1;
		}
		else if(m[next[j]] == m[j]){
			next[i++]=j+1;
			j=i-1;
		}
		else	j=next[j];
	}
//	
//	for(i=1;i<len_m;i++){
//		while(next[i]!=-1 && m[next[i]] == m[i])	next[i]=next[next[i]];
//	}
}

void solve(char* m,char* s,int len_m,int len_s){
	init_next(m,len_m);
	int i=0,j=0,cnt=0;
	while(i<len_s){
		if(j<len_m && (s[i]==m[j] || s[i]-m[j]=='a'-'A' || s[i]-m[j]=='A'-'a')){
			i++;
			j++;
		}
		else if(j==len_m){
			cnt++;
			j=next[j-1]+1;
		}
		else{
			j=next[j];
			if(j==-1)	i++;j=0;
		}
	}
	if(j==len_m)	cnt++;
	
	printf("%d\n",cnt);
}

int main(void)
{
	int t;
	scanf("%d",&t);
	int len_m,len_s;
	char m[MAXSIZE],s[MAXSIZE];
	while(t--){
		scanf("%d %d",&len_m,&len_s);
		getchar();
		gets(m);
		gets(s);
		
		solve(m,s,len_m,len_s);
	}
	
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...