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; }
|