题目链接：传送门

Description

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

Input

输入含多组数据。 每组数据的第一行为一个正整数N，表示共有N个模式串,1≤N≤150。 接下去N行，每行一个长度小于等于70的模式串。下一行是一个长度小于等于10^6的文本串T。 输入结束标志为N=0。

Output

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

Sample Input

2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0

Sample Output

4 aba 2 alpha haha

Solution

模板题，终于会AC自动机了

Code

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1000000 + 100;
int N;
struct ans
{
    char S[71];
    int cnt, pos;
}Ans[160];
struct Array
{
    int son[30], val, fail, last;
};
struct AC_automaton
{
    Array A[Maxn];
    int Cnt = 0;
    void Init(int x)
    {
        memset(A[x].son, 0, sizeof(A[x].son));
        A[x].fail = 0;
        A[x].last = 0;
        A[x].val =0;
    }
    void Insert(char *S, int num)
    {
        int len = strlen(S), now = 0;
        for (int i = 0; i < len; ++i)
        {
            if (!A[now].son[S[i] - 'a']) A[now].son[S[i] - 'a'] = ++Cnt, Init(Cnt);
            now = A[now].son[S[i] - 'a'];
        }
        A[now].val = num;
    }
    void Get_fail()
    {
        queue<int> Q;
        for (int i = 0; i < 26; ++i) if (A[0].son[i]) Q.push(A[0].son[i]), A[A[0].son[i]].fail = 0;
        while (!Q.empty())
        {
            int x = Q.front(); Q.pop();
            for (int i = 0; i < 26; ++i)
                if (A[x].son[i])
                {
                    A[A[x].son[i]].fail = A[A[x].fail].son[i];
                    if (A[A[A[x].fail].son[i]].val) A[A[x].son[i]].last = A[A[x].fail].son[i];
                    else A[A[x].son[i]].last = A[A[A[x].fail].son[i]].last;
                    Q.push(A[x].son[i]);
                }
                else A[x].son[i] = A[A[x].fail].son[i];
        }
    }
    void Calc(char *S)
    {
        int now = 0, len = strlen(S);
        for (int i = 0; i < len; ++i)
        {
            now = A[now].son[S[i] - 'a'];
            for (int x = now; x; x = A[x].last)
                Ans[A[x].val].cnt ++;
        }
    }
}AC;

inline int cmp(ans a, ans b)
{
    if (a.cnt == b.cnt) return a.pos < b.pos;
    return a.cnt > b.cnt;
}

char S[Maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (1)
    {
        scanf("%d", &N);
        if (!N) break;
        AC.Cnt = 0;
        AC.Init(0);
        for (int i = 1; i <= N; ++i)
        {
            scanf("%s", Ans[i].S);
            Ans[i].pos = i;
            Ans[i].cnt = 0;
            AC.Insert(Ans[i].S, i);
        }
        AC.Get_fail();
        scanf("%s", S);
        AC.Calc(S);
        sort(Ans + 1, Ans + N + 1, cmp);
        cout<<Ans[1].cnt<<endl;
        for (int i = 1; i <= N; ++i)
            if (Ans[i].cnt == Ans[1].cnt)
                cout<<Ans[i].S<<endl;
            else break;
    }
    return 0;
}