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
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int maxn = 1000010;
int n = 0, cnt = 0;
int trie[maxn][26], fail[maxn], isEnd[maxn];
string s, p[155];
int nums[155], ord[155];
bool cmp(int a, int b) {
if (nums[a] != nums[b])
return nums[a] < nums[b];
else return a > b;
}
void init() {
memset(trie, 0, sizeof(trie));
memset(fail, 0, sizeof(fail));
memset(isEnd, 0, sizeof(isEnd));
memset(nums, 0, sizeof(nums));
}
void insert(string& s, int num) {
int cur = 0, len = s.size();
for (int i = 0; i < len; i++) {
int ch = s[i] - 'a';
if (!trie[cur][ch])
trie[cur][ch] = ++cnt;
cur = trie[cur][ch];
}
isEnd[cur] = num;
}
void getFail() {
queue<int> q;
int cur = 0;
for (int i = 0; i < 26; i++)
if (trie[cur][i]) q.push(trie[cur][i]);
while (!q.empty()) {
cur = q.front(); q.pop();
for (int i = 0; i < 26; i++) {
if (trie[cur][i]) {
fail[trie[cur][i]] = trie[fail[cur]][i];
q.push(trie[cur][i]);
}
else trie[cur][i] = trie[fail[cur]][i];
}
}
}
void query(string& s) {
int len = s.size(), cur = 0;
for (int i = 0; i < len; i++) {
cur = trie[cur][s[i] - 'a'];
for (int j = cur; j; j = fail[j])
nums[isEnd[j]] += 1;
}
}
int main() {
ios::sync_with_stdio(false);
while (true) {
cin >> n;
if (n == 0) break;
init();
for (int i = 1; i <= n; i++) {
cin >> p[i];
ord[i] = i;
insert(p[i], i);
}
getFail();
cin >> s;
query(s);
sort(ord + 1, ord + n + 1, cmp);
int m = nums[ord[n]];
cout << m << '\n';
for (int i = n; i > 0; i--) {
if (nums[ord[i]] == m)
cout << p[ord[i]] << '\n';
else break;
}
}
return 0;
}
|
