板子题诶。
解法
AC 自动机模板题，因为数据范围比较小，所以不加拓扑排序优化建图即可通过本题。这里简单介绍一下拓扑排序优化建图。
在查找时，每次都暴力的条 $fail$ 指针是很消耗时间的，查找到了一个字符串可能意味着找到了多个字符串，例如我们有两个模式串 bc 和 abc，我们找到了串 abc，这同时意味着我们找到了串 bc，如果每次都去跳失配边的话效率过低，我们可以在找到一个模式串后打标记，最后进行拓扑排序求得最后的答案。
为什么可以使用拓扑排序？
因为失配边都是有向边，而失配边的起点一定比终点深度要深，而且不会存在自环。所以所有失配边所构成的图是一个有向无环图。
另外，这里建图不用真的把边都建出来，统计一下入度就行。
代码
#include<bits/stdc++.h>
namespace fast_IO
{
/**
* 快读快写。
*/
};
using namespace fast_IO;
class AC_auto
{
private:
#define LEN 1000001
#define N 200
int a[LEN][26],val[LEN],flag[LEN],fail[LEN],ind[LEN],cnt,tmp;
int ans[N],map[N];
std::deque<int> q;
public:
inline AC_auto()
{
memset(fail,0,sizeof(fail)),memset(val,0,sizeof(val)),memset(flag,0,sizeof(flag));
memset(a,0,sizeof(a)),memset(ind,0,sizeof(ind));
memset(ans,0,sizeof(ans)),memset(map,0,sizeof(map));
cnt=1;
}
inline void clear()
{
for(int i=0;i<=cnt;i++) memset(a[i],0,sizeof(a[i])),val[i]=flag[i]=fail[i]=ind[i]=0;
memset(ans,0,sizeof(ans)),memset(map,0,sizeof(map));
cnt=1;
}
inline void build()
{
for(int i=0;i<26;i++) a[0][i]=1;
q.push_back(1);
while(!q.empty())
{
tmp=q.front();q.pop_front();
for(int i=0;i<26;i++)
if(a[tmp][i])
fail[a[tmp][i]]=a[fail[tmp]][i],ind[fail[a[tmp][i]]]++,q.push_back(a[tmp][i]);
else a[tmp][i]=a[fail[tmp]][i];
}
}
inline void add(std::string st,int pos)
{
int now=1;
for(int i=0;i<st.size();i++)
{
if(!a[now][st[i]-'a']) a[now][st[i]-'a']=++cnt;
now=a[now][st[i]-'a'];
}
if(!flag[now]) flag[now]=pos;
map[pos]=flag[now];
}
inline void ask(std::string st)
{
int now=1;
for(int i=0;i<st.size();i++) now=a[now][st[i]-'a'],val[now]++;
}
inline void topo_sort()
{
for(int i=1;i<=cnt;i++) if(!ind[i]) q.push_back(i);
while(!q.empty())
{
tmp=q.front(),q.pop_front();
ans[flag[tmp]]=val[tmp],val[fail[tmp]]+=val[tmp];
if(!(--ind[fail[tmp]])) q.push_back(fail[tmp]);
}
}
inline std::vector<int> output(const int l,const int r)
{
std::vector<int> ret;
int maxi=0;
for(int i=l;i<=r;i++)
if(ans[map[i]]>maxi) maxi=ans[map[i]],ret.clear(),ret.push_back(i);
else if(ans[map[i]]==maxi) ret.push_back(i);
out<<maxi<<'\n';
return ret;
}
};
AC_auto ac_auto;
int n;
std::string s,t[200];
std::vector<int> v;
int main()
{
while(1)
{
in>>n;
if(n==0) break;
ac_auto.clear();
for(int i=1;i<=n;i++) in>>t[i],ac_auto.add(t[i],i);
ac_auto.build(),in>>s,ac_auto.ask(s),ac_auto.topo_sort(),v=ac_auto.output(1,n);
for(int i=0;i<v.size();i++) out<<t[v[i]]<<'\n';
}
fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
return 0;
}
