求助AC自动机
查看原帖
求助AC自动机
365532
Mr_ll楼主2022/8/5 16:53
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e6+10;
int n,tr[N][30],cnt,all[N],fail[N];
char s[200][80];

struct qwe
{
	int id,d;//id是下标,d是次数 
}ans[200];

bool pd()//输入 
{
	scanf("%d",&n);
	if(!n) return 0;
	else return 1;
}

bool cmp(qwe a,qwe b)//比较 
{
	if(a.d==b.d) return a.id<b.id;
	return a.d>b.d;
}

void clea()//清空 
{
	cnt=0;
	memset(tr,0,sizeof(tr));
	memset(all,0,sizeof(all));
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;i++) ans[i].id=i,ans[i].d=0;
}

int intt(char ch)//字符变数字 
{
	return ch-'a'+1;
}

void insert(int id,char *s)//插入 
{
	int l=strlen(s);
	int p=0;
	for(int i=0;i<l;i++)
	{
		int c=intt(s[i]);
		if(!tr[p][c])
			tr[p][c]=++cnt;
		p=tr[p][c];
	}
	all[p]=id;
}

void getfail()//处理fail数组 
{
	queue<int> q;
	for(int i=1;i<=26;i++)
	{
		if(tr[0][i])
			q.push(tr[0][i]);
	}
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=1;i<=26;i++)
		{
			if(tr[u][i])
				fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
			else 
				tr[u][i]=tr[fail[u]][i];
		}
	}
}

void query(char *t)//查询 
{
	int p=0;
	int l=strlen(t);
	for(int i=0;i<l;i++)
	{
		int c=intt(t[i]);
		p=tr[p][c];
		for(int j=p;j;j=fail[j])
		{
			ans[all[j]].d++;
		}
	}
//	cout<<"dsjlfa"<<endl;
//	for(int i=1;i<=n;i++) cout<<ans[i].d<<' ';
//	cout<<"sdf"<<endl;
	sort(ans+1,ans+1+n,cmp);//排序+输出 
	printf("%d\n",ans[1].d);
	for(int i=1;i<=n;i++)
	{
		if(ans[i].d!=ans[1].d) break;
		printf("%s\n",s[ans[i].id]);
	}
}

int main()
{
	while(pd())
	{
		clea();
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s[i]);
			insert(i,s[i]);
		}
		
		getfail();
		scanf("%s",s[n+1]);
		query(s[n+1]);
	}
	
	return 0;
}
2022/8/5 16:53
加载中...