蒟蒻求助,人都傻了,老是两个点调不出来
查看原帖
蒟蒻求助,人都傻了,老是两个点调不出来
215806
GodMan、、楼主2021/2/21 12:00
#include <bits/stdc++.h>
using namespace std;
#define godman main
#define N 1000001
#define SIZ 26
struct node{
	char c[71];
}ff[151];
struct Aho_Corasick_automaton{
	int cnt,ch[10000][SIZ],val[10000],last[10000],f[10000];int sum[10000];
	Aho_Corasick_automaton(){cnt=1;}	
	inline int idx(char c){
			return c-'a';
	}
	void insert(char s[],int v){
		int len=strlen(s);
		int u=0;
	
		for(int i=0;i<len;i++){
			int c=idx(s[i]);
			if(!ch[u][c]){
				memset(ch[++cnt],0,sizeof(ch[cnt]));
				ch[u][c]=cnt;
			}
			u=ch[u][c];
		}
		val[u]=v;
	}
	void getfail(){
		queue<int>q;
		for(int i=0;i<SIZ;i++)
			if(ch[0][i])q.push(ch[0][i]);
		while(!q.empty()){
			int r=q.front();q.pop();
			for(int i=0;i<SIZ;i++){
				int u=ch[r][i];
				if(!u){ch[r][i]=ch[f[r]][i];continue;}
				int v=f[r];
				f[u]=ch[v][i];
				last[u]=val[f[u]]?f[u]:last[f[u]];
				q.push(u);
			}
		}
	}
	void find(char t[]){
		int len=strlen(t);
		int u=0;
		for(int i=0;i<len;i++){
			int c=idx(t[i]);
			u=ch[u][c];
			if(val[u]){
				sum[val[u]]++;
			}
			int v=last[u];
			while(v){
				if(val[v]) sum[val[v]]++;
				v=last[v];
			}
		}
	}
	void goover(){
		memset(val,0,sizeof(val));
		memset(last,0,sizeof(last));
		memset(f,0,sizeof(f));
		memset(ch[0],0,sizeof(ch[0]));
		memset(sum,0,sizeof(sum));
		cnt=0;
	}
}AC;
int godwoman(){
	int n;cin>>n;
//	freopen("az.in","r",stdin);
//	freopen("az.out","w",stdout);
	while(n){
		
		for(int i=1;i<=n;i++)
			scanf("%s\n",ff[i].c),AC.insert(ff[i].c,i);
		AC.getfail();
		char t[N];scanf("%s",t);
		AC.find(t);
		int ans=0,flag;
		for(int i=1;i<=n;i++)
			if(AC.sum[i]>ans) ans=AC.sum[i];
		cout<<ans<<"\n";
		for(int i=1;i<=n;i++){
			if(AC.sum[i]==ans){
				for(int j=0;j<strlen(ff[i].c);j++)
				cout<<ff[i].c[j];
				cout<<endl;
			}
			
		}
			
		cin>>n;
		AC.goover();
	}
}
int godman(){
	return godwoman();
}
2021/2/21 12:00
加载中...