家人们谁懂啊,第一个点卡ab
查看原帖
家人们谁懂啊,第一个点卡ab
804108
__yelan__楼主2023/6/10 12:55
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int n,cnt=1,num[N],ans[155];
struct node{
	int son[26],index;
	int end,fail;
}t[N];
string str;
string ss[155];
void Insert(string s,int k){
	int now=0;
	for(int i=0;i<s.size();i++){
		int ch=s[i]-'a';
		if(t[now].son[ch]==0) t[now].son[ch]=cnt++;
		now=t[now].son[ch];
	}
	t[now].end++;
	num[now]=k;
}
void getfail(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(t[0].son[i]) q.push(t[0].son[i]);
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(t[now].son[i]){
				t[t[now].son[i]].fail=t[t[now].fail].son[i];
				q.push(t[now].son[i]);
			}
			else t[now].son[i]=t[t[now].fail].son[i];
		}

	}
}
void query(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		int ch=s[i]-'a';
		now=t[now].son[ch];
		int tmp=now;
		while(tmp&&t[tmp].end){
			ans[num[tmp]]++;
			tmp=t[tmp].fail;
		}
	}
}

int main(){
	while(true){
		scanf("%d",&n);
		if(n==0) break;
		memset(t,0,sizeof(t));
		memset(ans,0,sizeof(ans));
		memset(num,0,sizeof(num));
		for(int i=0;i<n;i++){
			cin>>ss[i];
			Insert(ss[i],i);
		}
		getfail();
		cin>>str;
		query(str);
		int tmp=0;
		for(int i=0;i<n;i++){
			if(ans[i]>tmp) tmp=ans[i];
		}
		printf("%d\n",tmp);
		for(int i=0;i<n;i++){
			if(ans[i]==tmp) cout<<ss[i]<<endl;
		}
		
	}
	return 0;
}
/*10
qabqks
vimbirqy
cflwvxtp
klljfj
ab
nkeiid
fkypjfev
yvgp
evdhs
xaizql
qabqksatffqpjomzstjabfklljfjqevdhsqabqkscflwvxtpeevdhsmzonkeiid
答案是3                           ab
我的是2
qabqks
evdhs                           
                                */ 
2023/6/10 12:55
加载中...