【题意】

【分析】

题目给出一个文本串多个模板串,要求出现最多的模板串。这恰好可以用AC自动机解决,只不过需要将print修改为cnt[val]++ 统计标号为val的模板串出现的次数。

 原理:在文本串不同位置出现的模板都可以通过自动机匹配找到。

 注意:为什么模板要开始从1标号? : 因为调用了insert(word[i],i)语句,如果给模板标号0的话相当于舍弃了这个模板串(val==0代表非单词结点),因此调用AhoCorasickaotomata的时候一定要注意不能把单词结点的val设为0。

【AC 代码】
//
//Created By just_sort 2016/8/20
//All Rights Reserved
//

#include <map>
#include <queue>
#include <string.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 11000;
const int maxs = 26;
const int maxm = 160;
map<string,int>mp;
struct acautomata{
    int nxt[maxn][maxs],fail[maxn],val[maxn],cnt[maxn];
    int root,sz;
    int newnode()
    {
        memset(nxt[sz],0,sizeof(nxt[sz]));
        val[sz] = 0;
        return sz++;
    }
    void init()
    {
        sz = 0;
        mp.clear();
        memset(cnt,0,sizeof(cnt));
        root = newnode();
    }
    void insert(char *P,int id){
        int u = root;
        int n = strlen(P);
        for(int i=0; i<n; i++){
            if(!nxt[u][P[i]-'a']){
                nxt[u][P[i]-'a'] = newnode();
            }
            u = nxt[u][P[i]-'a'];
        }
        val[u] = id;
        mp[string(P)] = id;
    }
    void build()
    {
        queue<int>q;
        fail[root]=0;
        int u;
        for(int i=0; i<maxs; i++){
            int &v = nxt[root][i];
            if(v){
                fail[v] = 0;
                q.push(v);
            }else{
                v = root;
            }
        }
        while(q.size()){
            u=q.front();q.pop();
            for(int i=0; i<maxs; i++){
                int &v = nxt[u][i];
                if(!v){
                    v = nxt[fail[u]][i];
                    continue;
                }
                q.push(v);
                fail[v] = nxt[fail[u]][i];
            }
        }
    }
    void query(char *T){
        int u = 0, n = strlen(T);
        int v;
        for(int i=0; i<n; i++){
            u = nxt[u][T[i]-'a'];
            v = u;
            cnt[val[v]]++;
        }
    }
}ac;
char text[1000010],P[151][80];
int main()
{
    int n;
    while(scanf("%d",&n)==1&&n){
        ac.init();
        for(int i=1; i<=n; i++){
            scanf("%s",P[i]);
            ac.insert(P[i],i);
        }
        ac.build();
        scanf("%s",text);
        ac.query(text);
        int maxx = -1;
        for(int i=1; i<=n; i++){
            if(ac.cnt[i]>maxx){
                maxx=ac.cnt[i];
            }
        }
        printf("%d\n",maxx);
        for(int i=1; i<=n; i++){
            if(ac.cnt[mp[string(P[i])]]==maxx) printf("%s\n",P[i]);
        }
    }
    return 0;
}