1 #include
     
       2 #include
      
        3 const int maxnode = 105000; //最大节点数 4 const int sigma_size = 26; //最大子节点数 5 int ch[maxnode][sigma_size]; //节点 6 int val[maxnode]; //节点信息 7 int sz; //节点总数 8 int idx(char c) { return c - 'a';} //返回节点编号 9 void Trie_init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); }10 int tot;11 int Trie_insert(char *s) {12     int u = 0;13     for(int i = 0; s[i]; ++i) {14         int c = idx(s[i]);15         if(!ch[u][c]) {16             memset(ch[sz], 0, sizeof(ch[sz]));17             val[sz] = 0;18             ch[u][c] = sz++;19         }20         u = ch[u][c];21     }22     if(val[u] == 0) return val[u] = ++tot;23     else return val[u];24 }25 int q[maxnode], f[maxnode], last[maxnode];26 void AC_getfail() {27     f[0] = 0;28     int front = 0, rear = -1;29     for(int c = 0; c < sigma_size; ++c) {30         int u = ch[0][c];31         if(u) { f[u] = 0; q[++rear] = u; last[u] = 0;}32     }33     while(front <= rear) {34         int r = q[front++];35         for(int c = 0; c < sigma_size; ++c) {36             int u = ch[r][c];37             if(!u) {ch[r][c] = ch[f[r]][c]; continue;}38             q[++rear] = u;39             int v = f[r];40             while(v && !ch[v][c]) v = f[v];41             f[u] = ch[v][c];42             last[u]= val[f[u]] ? f[u] : last[f[u]];43         }44     }45 }46 int cnt[151];47 void AC_print(int j) {48     if(j) {49         cnt[val[j]]++;50         AC_print(last[j]);51     }52 }53 void AC_find(char *s) {54   int j = 0;55   for(int i = 0; s[i]; ++i) {56       int c =idx(s[i]);57       j = ch[j][c];58       if(val[j]) AC_print(j);59       else if(last[j]) AC_print(last[j]);60   }61 }62 char text[1000001], p[151][80];63 int repi[151];64 int main() {65     int n;66     while(scanf("%d", &n) , n) {67         Trie_init();68         tot = 0;69         for(int i = 0; i < n; ++i) {70             scanf("%s", p[i]);71             repi[i] = Trie_insert(p[i]);72         }73         AC_getfail();74         scanf("%s", text);75         memset(cnt, 0, sizeof(cnt));76         AC_find(text);77         int max = -1;78         for(int i = 0; i < n; ++i) {79             if(cnt[repi[i]] > max) max = cnt[repi[i]];80         }81         printf("%d\n", max);82         for(int i = 0; i < n; ++i) {83             if(cnt[repi[i]] == max) printf("%s\n", p[i]);84         }85     }86     return 0;87 }