社区讨论
样例过了,但是测试点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 条回复,欢迎继续交流。
正在加载回复...