AC自动机

const int N = 1000005;
struct AC_Automaton {
    int tree_size, fail[N], nxt[N][26], exist[N];
    void insert(const string &str) {
        int len = str.size();
        int index = 0;
        for (int i = 0 ; i < len ; i++) {
            int c = str[i] - 'a';
            if (nxt[index][c] == 0) {
                nxt[index][c] = ++tree_size;
            }
            index = nxt[index][c];
        }
        exist[index]++;
    }
    void build() {
        queue<int> que;
        for (int i = 0 ; i < 26 ; i++) {
            if (nxt[0][i] != 0) {
                que.emplace(nxt[0][i]);
            } 
        }
        while (!que.empty()) {
            int index = que.front();
            que.pop();
            for (int i = 0 ; i < 26 ; i++) {
                if (nxt[index][i] != 0) {
                    fail[nxt[index][i]] = nxt[fail[index]][i];
                    que.emplace(nxt[index][i]);
                } else {
                    nxt[index][i] = nxt[fail[index]][i];
                }
            }
        }
    }
    int query(const string &str) {
        int len = str.size();
        int index = 0, res = 0;
        for (int i = 0 ; i < len ; i++) {
            int c = str[i] - 'a';
            index = nxt[index][c];
            for (int j = index ; j != 0 && exist[j] != -1 ; j = fail[j]) {
                res += exist[j];
                exist[j] = -1;
            }
        }
        return res;
    }
}; // AC_Automaton
int main() {
    int n;
    cin >> n;
    AC_Automaton *ac = new AC_Automaton();
    string str;
    for (int i = 0 ; i < n ; i++) {
        cin >> str;
        ac -> insert(str);
    }
    ac -> build();
    cin >> str;
    cout << (ac -> query(str));
    return 0;
}

const int N = 151;
const int M = N * 70;
struct AC_Automaton {
    int tree_size, fail[M], nxt[M][26], val[M], idx[M];
    int cnt[N];
    void insert(const string &str, int pos) {
        int len = str.size();
        int index = 0;
        for (int i = 0 ; i < len ; i++) {
            int c = str[i] - 'a';
            if (nxt[index][c] == 0) {
                nxt[index][c] = ++tree_size;
            }
            index = nxt[index][c];
        }
        idx[index] = pos;
    }
    void build() {
        queue<int> que;
        for (int i = 0 ; i < 26 ; i++) {
            if (nxt[0][i] != 0) {
                que.emplace(nxt[0][i]);
            } 
        }
        while (!que.empty()) {
            int index = que.front();
            que.pop();
            for (int i = 0 ; i < 26 ; i++) {
                if (nxt[index][i] != 0) {
                    fail[nxt[index][i]] = nxt[fail[index]][i];
                    que.emplace(nxt[index][i]);
                } else {
                    nxt[index][i] = nxt[fail[index]][i];
                }
            }
        }
    }
    int query(const string &str) {
        int len = str.size();
        int index = 0, res = 0;
        for (int i = 0 ; i < len ; i++) {
            int c = str[i] - 'a';
            index = nxt[index][c];
            for (int j = index ; j != 0 ; j = fail[j]) {
                val[j]++;
            }
        }
        for (int i = 1 ; i <= tree_size ; i++) {
            if (idx[i] == 0) continue;
            res = max(res, val[i]);
            cnt[idx[i]] = val[i];
        }
        return res;
    }
}; // AC_Automaton
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    AC_Automaton *ac = new AC_Automaton();
    while (cin >> n) {
        if (n == 0) break;
        vector<string> s(n + 1);
        for (int i = 1 ; i <= n ; i++) {
            cin >> s[i];
            ac -> insert(s[i], i);
        }
        ac -> build();
        string str;
        cin >> str;
        int ans = ac -> query(str);
        cout << ans << "\n";
        for (int i = 1 ; i <= n ; i++) {
            if (ac -> cnt[i] == ans) {
                cout << s[i] << "\n";
            }
        }
        for (int i = 0 ; i <= (ac -> tree_size) ; i++) {
            ac -> fail[i] = 0;
            ac -> val[i] = 0;
            ac -> idx[i] = 0;
            for (int j = 0 ; j < 26 ; j++) {
                ac -> nxt[i][j] = 0;
            }
        }
        ac -> tree_size = 0;
        for (int i = 1 ; i <= n ; i++) {
            ac -> cnt[i] = 0;
        }
    }
    return 0;
}