AC自动机模板

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;using LL = long long;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}template 
     
      inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }template 
      
       inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 200;const int M = 100005;int n, tot, cnt, trie[M][26], ending[M], iex[N], fail[M], freq[M], head[M];string s[N], t;struct Edge { int v, next; } edge[M<<1];void addEdge(int a, int b){    edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;}void init(){    tot = cnt = 0;    full(ending, 0), full(iex, 0), full(freq, 0);    full(trie, 0), full(head, -1);}void insert(const string &buf, int j){    int p = 0;    for(int i = 0; i < buf.size(); i ++){        int ch = buf[i] - 'a';        if(!trie[p][ch]) trie[p][ch] = ++ tot;        p = trie[p][ch];    }    ending[p] ++, iex[j] = p;}void getFail(){    full(fail, 0);    queue
       
         q;    for(int i = 0; i < 26; i ++){        if(trie[0][i]) q.push(trie[0][i]);    }    while(!q.empty()){        int s = q.front(); q.pop();        for(int i = 0; i < 26; i ++){            if(trie[s][i]){                fail[trie[s][i]] = trie[fail[s]][i];                q.push(trie[s][i]);            }            else trie[s][i] = trie[fail[s]][i];        }    }}void buildFailTree(){    for(int i = 1; i <= tot; i ++){        addEdge(fail[i], i), addEdge(i, fail[i]);    }}void dfs(int s, int fa){    for(int i = head[s]; i != -1; i = edge[i].next){        int u = edge[i].v;        if(u == fa) continue;        dfs(u, s);        freq[s] += freq[u];    }}void query(const string &buf){    int p = 0, maxl = 0;    for(int i = 0; i < buf.size(); i ++){        p = trie[p][buf[i] - 'a'];        freq[p] ++;    }    dfs(0, 0);    for(int i = 1; i <= n; i ++){        maxl = max(maxl, freq[iex[i]]);    }    cout << maxl << endl;    for(int i = 1; i <= n; i ++){        if(maxl == freq[iex[i]]){            cout << s[i] << endl;        }    }}int main(){    __fastIn;    while(cin >> n && n){        init();        for(int i = 1; i <= n; i ++){            cin >> s[i];            insert(s[i], i);        }        getFail(), buildFailTree();        cin >> t;        query(t);    }    return 0;}