wa on #2求调
查看原帖
wa on #2求调
374756
忘怜城羡楼主2023/11/28 21:46
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+7;
char ch[MAXN];
struct node{
	int nxt[27],fail,sum;
}trie[MAXN<<2];
int tot=0;
void getfail()
{
	queue<int> q;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i(1);i<=26;++i)
		{
			if(trie[u].nxt[i]!=0)
			{
				trie[trie[u].nxt[i]].fail=trie[trie[u].fail].nxt[i];
				q.push(trie[u].nxt[i]);
			}
			else
			trie[u].nxt[i]=trie[trie[u].fail].nxt[i];
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i(1);i<=n;++i)
	{
		cin>>ch+1;
		int len=strlen(ch+1);
		int nowid=0;
		for(int j(1);j<=len;++j)
		{
			if(!trie[nowid].nxt[ch[j]-'a'+1])
			{
				trie[nowid].nxt[ch[j]-'a'+1]=++tot;
				nowid=tot;
			}
			else
			nowid=trie[nowid].nxt[ch[j]-'a'+1];
		}
		trie[nowid].sum++;
	}
	trie[0].fail=0;
	getfail();
	cin>>ch+1;
	int len=strlen(ch+1);
	int nowid=0,ans=0;
	for(int i(1);i<=len;++i)
	{
		nowid=trie[nowid].nxt[ch[i]-'a'+1];
		int cnt=nowid;
		while(cnt&&trie[cnt].sum!=-1)
		{
			ans+=trie[cnt].sum;
			trie[cnt].sum=-1;
			cnt=trie[cnt].fail;
		}
	}
	printf("%d",ans);
}
2023/11/28 21:46
加载中...