题目描述

有NNN个由小写字母组成的模式串以及一个文本串TTT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TTT中出现的次数最多。

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数NNN，表示共有NNN个模式串，1≤N≤1501 \leq N \leq 1501≤N≤150。

接下去NNN行，每行一个长度小于等于707070的模式串。下一行是一个长度小于等于10610^6106的文本串TTT。

输入结束标志为N=0N=0N=0。

输出格式：

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

输入输出样例

2

aba

bab

ababababac

6

beta

alpha

haha

delta

dede

tata

dedeltalphahahahototatalpha

0

4

aba

2

alpha

haha

//by 减维

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<map>

#include<bitset>

#include<algorithm>

#define ll long long

#define maxn 1000005

using namespace std;

struct trie{

    int end,fail,to[];

    void cle(){

        memset(to,,sizeof(to));

        end=fail=;

    }

}ac[maxn];

struct anss{

    int pos,num;

}ans[maxn];

int n,tot;

string s[];

bool cmp(const anss&x,const anss&y)

{

    if(x.num==y.num)return x.pos<y.pos;

    return x.num>y.num;

}

void build(int x)

{

    int now=,ch;

    int len=s[x].length();

    for(int i=;i<len;++i)

    {

        ch=s[x][i]-'a';

        if(!ac[now].to[ch])ac[now].to[ch]=++tot,ac[tot].cle();

        now=ac[now].to[ch];

    }

    ac[now].end=x;

}

void getf()

{

    queue<int>q;

    for(int i=;i<;++i)

        if(ac[].to[i])q.push(ac[].to[i]),ac[ac[].to[i]].fail=;

    while(!q.empty())

    {

        int d=q.front();

        q.pop();

        for(int i=;i<;++i)

        {

            int dd=ac[d].to[i];

            if(dd)ac[dd].fail=ac[ac[d].fail].to[i],q.push(dd);

            else ac[d].to[i]=ac[ac[d].fail].to[i];

        }

    }

}

void ask()

{

    int now=,ch;

    int len=s[].length();

    for(int i=;i<len;++i)

    {

        ch=s[][i]-'a';

        now=ac[now].to[ch];

        for(int j=now;j;j=ac[j].fail)

            if(ac[j].end)ans[ac[j].end].num++;

    }

    sort(ans+,ans++n,cmp);

    printf("%d\n",ans[].num);

    for(int i=;i<=n;++i)

        if(ans[i].num==ans[].num)cout<<s[ans[i].pos]<<endl;

        else break;

}

int main()

{

    while()

    {

        scanf("%d",&n);

        if(n==)return ;

        tot=;ac[].cle();

        for(int i=;i<=n;++i)

        {

            cin>>s[i];

            build(i);

            ans[i].pos=i;

            ans[i].num=;

        }

        getf();

        cin>>s[];

        ask();

    }

}