大佬们不知道为什么编译失败!!!
查看原帖
大佬们不知道为什么编译失败!!!
226367
glorious_dream楼主2021/9/14 20:14
#include<bits/stdc++.h>
using namespace std;
const int M = 500010;
char s[M*2];
int ch[M][30],bo[M],que[M],next[M];
int ans,cnt=1;
void make(char *s){
	int u=1 ; 
	int len = strlen(s);
	for(int i=0 ; i<len ; i++){
		int c = s[i]-'a';
		if(!ch[u][c]){
			ch[u][c] = ++cnt;
			memset(ch[cnt],0,sizeof(ch[cnt]));
		}
		u = ch[u][c];
	}
	bo[u]++;
	return;
}
void bfs(){
	for(int i=0 ; i<=25 ; i++){
		ch[0][i] = 1;
	}
	que[1] = 1;
	next[1] = 0;
	for(int q1=1,q2=1 ; q1<=q2 ; q1++){
		int u = que[q1];
		for(int i=0 ; i<=25 ; i++){
			if(!ch[u][i]){
				ch[u][i] = ch[next[u]][i];
			}
			else{
				que[++q2] = ch[u][i];
				int v = next[u];
				next[ch[u][i]] = ch[v][i];
			}
		}
	}
}
void find(char *s){
	int u=1;
	int len = strlen(s);
	int c,k;
	for(int i=0 ; i<len ; i++){
		c = s[i]-'a';
		k = ch[u][c];
		while(k>1){
			ans+=bo[k];
			bo[k] = 0;
			k = next[k];
		}
		u = ch[u][c];
	}
	return;
}
int n;
int main(){
	scanf("%d",&n);
	for(int i=0 ; i<26 ; i++){
		ch[0][i] = 1;
		ch[1][i] = 0;
	}
	for(int i=1 ; i<=n ; i++){
		scanf("%s",s);
		make(s);
	}
	bfs();
	scanf("%s",s);
	find(s);
	printf("%d",ans);
	return 0;
}

2021/9/14 20:14
加载中...