qiutiao
查看原帖
qiutiao
1419569
Z_kazuha楼主2024/11/5 20:41
#include <bits/stdc++.h>
using namespace std;
const int N=155;
int t,n,cnt,vis[N],ans;
string s,b[N];
struct node{
	int son[27],end,fail;
}trie[N];
void build(int num){
	int now=0;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		if(!trie[now].son[c])trie[now].son[c]=cnt++;
		now=trie[now].son[c];
	}
	trie[now].end=num;
	//cout<<trie[now].end<<endl;
}
void bfs(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(trie[0].son[i]){
			q.push(trie[0].son[i]);
		}
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(trie[now].son[i]){
				trie[trie[now].son[i]].fail=trie[trie[now].fail].son[i];
				q.push(trie[now].son[i]);
			}else{
				trie[now].son[i]=trie[trie[now].fail].son[i];
			}
		}
	}
}
void query(){
	int now=1;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		int tmp=trie[now].son[c];
		while(tmp>1){
			if(trie[tmp].end)vis[trie[now].end]++;
			tmp=trie[tmp].fail;
			cout<<trie[now].end<<endl;
		}
        now=trie[now].son[c];
	}
}
int main(){
    cin>>n;
	while(n){
		memset(trie,0,sizeof(trie));
		cnt=1;
		ans=0;
		for(int i=1;i<=n;i++){
			cin>>s;
            b[i]=s;
			build(i);
		}
		bfs();
		cin>>s;
        query();
        for(int i=1;i<=n;i++)ans=max(vis[i],ans);
        cout<<ans<<endl;
        for(int i=1;i<=n;i++){
            if(vis[i]==ans)cout<<b[i]<<endl;
        }
        cin>>n;
	}
	return 0;
}
2024/11/5 20:41
加载中...