为什么多写个没有用过的数组才能AC
查看原帖
为什么多写个没有用过的数组才能AC
546012
mujiajun楼主2024/7/18 20:08
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,last[200005],f[200005],tr[200005][30],v[200005],sum[200005],maxn,tot,ans[200005],flag[200005],in[200005]/*,vis[200005]*/;
char st1[200005],st2[1000005];
void insert(char* st,int va)
{
	int len=strlen(st),p=0;
	for(int i=0;i<len;i++)
	{
		int ch=st[i]-'a'+1;
		if(!tr[p][ch])
		{
			memset(tr[++tot],0,sizeof(tr[tot]));
			tr[p][ch]=tot;
		}
		p=tr[p][ch];
	} 
	flag[va]=p;
}
void getpre()
{
	queue<int> q;
	for(int i=1;i<=26;i++)
		if(tr[0][i])	q.push(tr[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=1;i<=26;i++)
		{
			if(!tr[x][i])
			{
				tr[x][i]=tr[f[x]][i];
				continue;
			}
			f[tr[x][i]]=tr[f[x]][i];
			in[f[tr[x][i]]]++;
			q.push(tr[x][i]);
		//	printf("%d ",tr[x][i]);
		}
	}
}
void find(char* st)
{
	int len=strlen(st),p=0;
	for(int i=0;i<len;i++)
	{
		int ch=st[i]-'a'+1;
		p=tr[p][ch];
		ans[p]++;
	}
}
void topu()
{
	queue<int> q;
	for(int i=1;i<=tot;i++)
		if(!in[i])	q.push(i);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		int u=f[x];
		ans[u]+=ans[x];
		if(!(--in[u]))	q.push(u);
	}
}
int main()
{
	scanf("%d",&n);
	if(n==0)return 0;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",st1);
		insert(st1,i);
	}
	getpre();
	scanf("%s",st2);
	find(st2);
	topu();
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[flag[i]]);
	return 0;
}
为什么我把vis数组注释掉就不对了,我其他地方完全没有用过vis数组??
我把vis数组写上,就AC了
2024/7/18 20:08
加载中...