悬5关AC自动机板子洛谷IDEAC本机洛谷测评机CE求调
查看原帖
悬5关AC自动机板子洛谷IDEAC本机洛谷测评机CE求调
532109
freedom_wang楼主2024/7/22 17:27
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rop(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define por(i,a,b) for(int i=a;i>b;i--)
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double ld;
using namespace std;
int t,n,cnt,rev[8000005],indeg[8000005],ans,vis[8000005],mx;
char s[8000005],s1[155][8000005];
bool x[8000005];
struct node{
	int fail,ans,son[26],flag;
	void init(){
		memset(son,0,sizeof(son));
		fail=flag=ans=0;
	}
}trie[8000005];
queue<int>q;
void insert(char*s,int num){
	int u=1,len=strlen(s);
	rop(i,0,len){
		int to=s[i]-97;
		if(!trie[u].son[to])
			trie[u].son[to]=++cnt;
		u=trie[u].son[to];
	}
	if(!trie[u].flag)
		trie[u].flag=num;
	rev[num]=trie[u].flag;
}
void getfail(){
	rop(i,0,26)
		trie[0].son[i]=1;
	q.push(1);
	trie[1].fail=0;
	while(q.size()){
	    int u=q.front();
	    q.pop();
	    int fail=trie[u].fail;
	    rop(i,0,26){
			int to=trie[u].son[i];
			if(!to){
				trie[u].son[i]=trie[fail].son[i];
				continue;
			}
			trie[to].fail=trie[fail].son[i];
			indeg[trie[fail].son[i]]++;
			q.push(to);
	    }
	}
}
void topu(){
	rep(i,1,cnt)
		if(!indeg[i])
			q.push(i);
	while(q.size()){
		int fr=q.front();
		q.pop();
		vis[trie[fr].flag]=trie[fr].ans;
		int u=trie[fr].fail;
		trie[u].ans+=trie[fr].ans;
		if((--indeg[u])==0)
			q.push(u);
	} 
}
void query(char*s){
	int u=1,len=strlen(s);
	rop(i,0,len){
		u=trie[u].son[s[i]-97];
		trie[u].ans++;
	}
}
void solve(){
	rep(i,0,cnt)
		trie[i].init();
	rep(i,1,n)
		vis[i]=0;
	cnt=1;
	ans=mx=0;
	rep(i,1,n){
		cin>>s;
		memcpy(s1[i],s,strlen(s));
		insert(s,i);
	} 
	getfail();
	cin>>s;
	query(s);
	topu();
	rep(i,1,n)
		mx=max(mx,vis[rev[i]]); 
	cout<<mx<<endl;
	rep(i,1,n){
		if(vis[rev[i]]==mx)
			cout<<s1[i]<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	while(1){
		cin>>n;
		if(n==0)
			break;
		solve();
	}
	return 0;
}
/*
?现在jc方式那么低级啊
*/

2024/7/22 17:27
加载中...