求助
查看原帖
求助
317915
陈思行楼主2021/3/6 22:47

T了一个点,还有一个RE

#include<bits/stdc++.h>
using namespace std;
int t,n;
string s,ss;
int ch[1000005][30],bo[1000005],c,u,l,tot=1;//tire
int dui[1000005],head,tail;//bfs
int ans,next[1000005];//find
void tire() {
	cout<<1;
	l=ss.size();
	u=1;
	for(int i=0; i<l; i++) {
		c=ss[i]-'a';
		if(!ch[u][c])ch[u][c]=++tot;
		u=ch[u][c];
	}
	bo[u]++;
	return ;
}
void bfs() {
	for(int k=0; k<=25;k++) {
		ch[0][k]=1;
	}
	dui[1]=1;
	next[1]=0;
	while(head<=tail) {
		u=dui[head];
		for(int i=0; i<=25; i++) {
			if(!ch[u][i])ch[u][i]=ch[next[u]][i];
			else {
				dui[++tail]=ch[u][i];
				next[ch[u][i]]=ch[next[u]][i];
			}
		}
		head++;
	}
	return ;
}
void find() {
	u=1;
	l=s.size();
	int k;
	for(int i=0; i<l; i++) {
		c=s[i]-'a';
		k=ch[u][c];
		while(k>1) {
			ans+=bo[k];
			bo[k]=0;
			k=next[k];
		}
	}
	return ;
}
int main() {
	cin>>n;
	for(int j=1; j<=n; j++) {
		cin>>ss;
		tire();
	}
	u=1;
	bfs();
	cin>>s;
	find();
	cout<<ans<<endl;
	//cout<<1;}
	return 0;
}

代码是不是有错误

2021/3/6 22:47
加载中...