萌新刚学ACAM,求调
查看原帖
萌新刚学ACAM,求调
203008
山田リョウ楼主2021/11/4 22:34

rt,只有50pts,WA了第二个点。

#include<stdio.h>
#include<string.h>
struct{
	int ch[26],fail,cnt;
}acam[1000001];int tot,ans;
void insert(char s[],int n){
	int x=0;
	for(int i=0;i<n;++i){
		if(!acam[x].ch[s[i]-'a'])acam[x].ch[s[i]-'a']=++tot;
		x=acam[x].ch[s[i]-'a'];
	}
	++acam[x].cnt;
}
void bfs(){
	static int q[1000001];
	for(int l=0,r=1;l<r;++l)
		for(int c=0;c<26;++c){
			int x=acam[q[l]].ch[c];
			if(!x){acam[q[l]].ch[c]=acam[acam[q[l]].fail].ch[c];}
			else{
				q[r++]=x;
				acam[x].fail=acam[acam[q[l]].fail].ch[c];
			}
		}
}
void find(char s[],int n){
	int x=0;
	for(int i=0;i<n;++i)x=acam[x].ch[s[i]-'a'],ans+=acam[x].cnt,acam[x].cnt=0;
}
char s[1000001];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;++i)scanf("%*c%s",s),insert(s,strlen(s));
	bfs();
	scanf("%*c%s",s);
	find(s,strlen(s));
	printf("%d",ans);
	return 0;
}
2021/11/4 22:34
加载中...