AC自动机求调
查看原帖
AC自动机求调
377440
Y2y7m楼主2022/5/23 15:13
#include <bits/stdc++.h>

using namespace std;
struct node
{
    int son[30];
    int fail;
    int id;
}trie[3000010];
struct answer
{
	int id,x;
}ans[100010];
bool cmp(answer x,answer y)
{
	if(x.x!=y.x)
		return x.x>y.x;
	return x.id<y.id;
}
int cnt;
int root;
void insert(char *s,int id)
{
    int pos=root;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        int t=s[i]-'a'+1;
        if(!trie[pos].son[t])
        	trie[pos].son[t]=++cnt;
        pos=trie[pos].son[t];
    }
    trie[pos].id=id;
}
void buildfail()
{
	queue<int> q;
	for(int i=1;i<=26;i++)
		if(trie[0].son[i])
			q.push(trie[0].son[i]),trie[trie[0].son[i]].fail=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=1;i<=26;i++)
		{
			int v=trie[u].son[i];
			int fail=trie[u].fail; 
			if(!v)
			{
				trie[u].son[i]=trie[fail].son[i];
				continue;
			}
			trie[v].fail=trie[fail].son[i];
			q.push(v);
		}
	}
}
void query(char* s)
{
	int u=root;
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)
	{
		int v=s[i]-'a'+1;
		int pos=trie[u].son[v];
		
		while(pos)
		{
			ans[trie[pos].id].x++;
			pos=trie[pos].fail;
			
		}
		u=trie[u].son[v];
	}
}
char s[2000][80];
char tmp[1000010];
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0)
			break;
		for(int i=1;i<=80;i++)
			ans[i].id=0,ans[i].x=0;
		for(int i=0;i<=cnt;i++)
		{
			for(int j=0;j<=26;j++)
				trie[i].son[j]=0;
			trie[i].fail=0;
			trie[i].id=0;
		}
		for(int i=1;i<=n;i++)
			ans[i].id=i;
		cnt=0;
		for(int i=1;i<=n;i++)
		{
			//cout<<"t"<<endl;
			cin>>s[i]+1;
			insert(s[i],i);
		}
		buildfail();
		cin>>tmp+1;
		query(tmp);
		sort(ans+1,ans+1+n,cmp);
		cout<<ans[1].x<<endl<<s[ans[1].id]+1<<endl;
		for(int i=2;i<=n;i++)
		{
			if(ans[i].x==ans[i-1].x)
			{
				cout<<s[ans[i].id]+1<<endl;				
			}
			else
				break;
		}
	}

	return 0;
}
2022/5/23 15:13
加载中...