题面
建出AC自动机
注意一下,这里不能每次暴跳
每次访问到cnt++
最后桶排从深到浅更新答案就好了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
using namespace std; char m[160][80],t[1000010]; int cou[160]; struct { struct triedata{ int son[27]; int fail,end; int& operator[](char x){return son[x-'a'];} }t[1000010]; int tot; void add(int end){ char*s=m[end]; int len=strlen(s),now=0; for(int i=0;i<len;i++)now=(t[now][s[i]]?t[now][s[i]]:t[now][s[i]]=++tot); t[now].end=end; } void clear(){memset(this,0,sizeof(AC));} void failready(){ queue<int>q; q.push(0); t[0].fail=-1; while(!q.empty()){ int now=q.front();q.pop(); for(char i='a';i<='z';i++) if(t[now][i])t[t[now][i]].fail=now?t[t[now].fail][i]:0,q.push(t[now][i]); else t[now][i]=t[t[now].fail][i]; } } void work(char* s); }ac; void AC::work(char* s){ int len=strlen(s); int now=0; for(int i=0;i<len;i++){ now=t[now][s[i]]; int p=now; while(~p){ cou[t[p].end]++; p=t[p].fail; } } } int n; int main(){ while(1){ ac.clear(); memset(cou,0,sizeof(cou)); scanf("%d",&n); if(n==0)return 0; for(int i=1;i<=n;i++){ scanf("%s",m[i]); ac.add(i); } ac.failready(); scanf("%s",t); ac.work(t); int ans=0; for(int i=1;i<=n;i++)ans=max(ans,cou[i]); printf("%dn",ans); for(int i=1;i<=n;i++)if(cou[i]==ans)puts(m[i]); } }
|
近期评论