MnZn板子求调,only ac on #11
查看原帖
MnZn板子求调,only ac on #11
374756
忘怜城羡楼主2023/12/4 20:31

rt

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+7;
int tot,ans,num[MAXN];
char ch[MAXN];
struct node{
	int nxt[27],fail,op;
	void clear()
	{
		for(int i(0);i<=26;++i)
		nxt[i]=0;
		fail=op=0;
	}
}trie[MAXN<<2];
string str[MAXN];
void getfail()
{
	queue<int> q;
	trie[0].fail=0;
	for(int i(1);i<=26;++i)
		if(trie[0].nxt[i])
		{
			trie[trie[0].nxt[i]].fail=0;
			q.push(trie[0].nxt[i]);
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i(1);i<=26;++i)
		{
			if(trie[u].nxt[i])
			{
				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);
	while(n)
	{
		for(int i(0);i<=tot;++i)
			trie[i].clear();
		tot=0;
		for(int i(1);i<=n;++i)
		{
			num[i]=0;
			cin>>ch+1;
			str[i]=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]==0)
				{
					trie[nowid].nxt[ch[j]-'a'+1]=++tot;
					nowid=tot;
				}
			}
			trie[nowid].op=i;
		}
		getfail();
		cin>>ch+1;
		int len=strlen(ch+1),nowid=0;
		ans=0;
		for(int i(1);i<=len;++i)
		{
			nowid=trie[nowid].nxt[ch[i]-'a'+1];
			int cnt=nowid;
			while(cnt)
			{
				if(trie[cnt].op)
				{
					num[trie[cnt].op]++;
					ans=max(ans,num[trie[cnt].op]);
				}
				cnt=trie[cnt].fail;
			}
		}
		printf("%d\n",ans);
		for(int i(1);i<=n;++i)
			if(num[i]==ans)
				cout<<str[i]<<"\n";
		scanf("%d",&n);
	}
}
2023/12/4 20:31
加载中...