题解
-
考虑如何计数：
-
我们在建树的过程中记录每个模式串的结束位置 \(End_i\)。
-
在文本串匹配时，每跑到一个结束位置，就将其对应的 \(cnt\) 加一即可。
-
-
询问与统计答案：
-
询问：不同于简单版 I，每个串每出现一次都要统计，不能提前结束。
-
统计答案：所有模式串枚举一遍，看哪个是最大值即可。
-
注：多测不清空，十年 OI 一场空。
::::success[代码]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=205,L=1e6+5;
int n,ans,rt=0,cid;
string s[N],t;
int fail[N];//fail[i]指向 从根开始的某个字符串的前缀，满足这个前缀等于i所在的后缀，且最长
int End[N];//End数组标记每个模式串在trie树的结束点
int cnt[N];//记每个结束点访问的次数
void insert(string a,int id){int pos=rt;for(int i=0;i<a.size();i++){int c=a[i]-'a';if(tr[pos][c]==0) tr[pos][c]=++cid;pos=tr[pos][c];}End[pos]=id;
}
void getfail(){//BFS,利用BFS层次单调性更新下一层queue <int> q;for(int i=0;i<26;i++){if(tr[rt][i]) q.push(tr[rt][i]);}while(!q.empty()){int f=q.front();q.pop();for(int i=0;i<26;i++){int son=tr[f][i];if(son){//如果儿子节点是存在的，则将儿子指向它对应的从根节点开始的最长前缀fail[son]=tr[fail[f]][i];q.push(son);}else{//如果儿子节点不存在，直接指向 f 在另一串对应的子结点tr[f][i]=tr[fail[f]][i];}}}
}
void query(string a){int pos=rt;for(int i=0;i<a.size();i++){int c=a[i]-'a';pos=tr[pos][c];//pos走a串的，不能用于跳failint u=pos;//不同于简单版 I，每个串每出现一次都要统计，不能提前结束while(u!=rt){cnt[End[u]]++;u=fail[u];}}
}
void init(){cid=0;ans=0;memset(tr,0,sizeof tr);memset(End,0,sizeof End);memset(cnt,0,sizeof cnt);memset(fail,0,sizeof fail);for(int i=1;i<=n;i++){cin>>s[i];insert(s[i],i);}getfail();cin>>t;query(t);for(int i=1;i<=n;i++){ans=max(ans,cnt[i]);}printf("%d\n",ans);for(int i=1;i<=n;i++){if(cnt[i]==ans) cout<<s[i]<<'\n';}
}
int main(){while(cin>>n&&n){init();}
}
/*
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
*/
::::
一点点扩展
如果要统计每种模式串出现的数目，可以将相同模式串映射到同一个 \(cnt\) 内。
更新 \(cnt\) 操作同上，统计答案使用映射获取每个模式串的 \(cnt\) 即可。