题目传送门

　　传送门I

　　传送门II

题目大意

　　给定$n$个串，询问所有出现在严格大于$\frac{n}{2}$个串的最长串。不存在输出'?'

 /**

  * poj

  * Problem#3294

  * Accepted

  * Time: 391ms

  * Memory: 5024k

  */

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #ifndef WIN32

 #define Auto "%lld"

 #else

 #define Auto "%I64d"

 #endif

 using namespace std;

 typedef bool boolean;

 #define ll long long

 #define pii pair<int, int>

 #define fi first

 #define sc second

 const int N = 1e5 + , M = ;

 typedef class Pair3 {

     public:

         int x, y, id;

         Pair3() {    }

         Pair3(int x, int y, int id):x(x), y(y), id(id) {    }

 }Pair3;

 typedef class SuffixArray {

     protected:

         Pair3 T1[N], T2[N];

         int cnt[N];

     public:

         int n;

         char *str;

         int sa[N], rk[N], hei[N];

         void set(int n, char* str) {

             this->n = n;

             this->str = str;

             memset(sa, , sizeof(sa));

             memset(rk, , sizeof(rk));

             memset(hei, , sizeof(hei));

         }

         void radix_sort(Pair3* x, Pair3* y) {

             int m = max(n, );

             memset(cnt, , sizeof(int) * m);

             for (int i = ; i < n; i++)

                 cnt[x[i].y]++;

             for (int i = ; i < m; i++)

                 cnt[i] += cnt[i - ];

             for (int i = ; i < n; i++)

                 y[--cnt[x[i].y]] = x[i];

             memset(cnt, , sizeof(int) * m);

             for (int i = ; i < n; i++)

                 cnt[y[i].x]++;

             for (int i = ; i < m; i++)

                 cnt[i] += cnt[i - ];

             for (int i = n - ; ~i; i--)

                 x[--cnt[y[i].x]] = y[i];

         }

         void build() {

             for (int i = ; i < n; i++)

                 rk[i] = str[i];

             for (int k = ; k < n; k <<= ) {

                 for (int i = ; i + k < n; i++)

                     T1[i] = Pair3(rk[i], rk[i + k], i);

                 for (int i = n - k; i < n; i++)

                     T1[i] = Pair3(rk[i], , i);

                 radix_sort(T1, T2);

                 int diff = ;

                 rk[T1[].id] = ;

                 for (int i = ; i < n; i++)

                     rk[T1[i].id] = (T1[i].x == T1[i - ].x && T1[i].y == T1[i - ].y) ? (diff) : (++diff);

                 if (diff == n - )

                     break;

             }

             for (int i = ; i < n; i++)

                 sa[rk[i]] = i;

         }

         void get_height() {

             for (int i = , j, k = ; i < n; i++, (k) ? (k--) : ()) {

                 if (rk[i]) {

                     j = sa[rk[i] - ];

                     while (i + k < n && j + k < n && str[i + k] == str[j + k])    k++;

                     hei[rk[i]] = k;

                 }

             }

         }

         const int& operator [] (int p) {

             return sa[p];

         }

         const int& operator () (int p) {

             return hei[p];

         }

 }SuffixArray;

 int n, m, K;

 char S[N];

 int suf[N];

 SuffixArray sa;

 inline boolean init() {

     scanf("%d", &m);

     if (!m)

         return false;

     K = (m >> ) + ;

     scanf("%s", S);

     n = strlen(S);

     for (int i = ; i < m; i++) {

         S[n++] = '?';

         scanf("%s", S + n);

         n += strlen(S + n);

     }

     suf[n] = ;

     for (int i = n - ; ~i; i--)

         suf[i] = suf[i + ] + (S[i] == '?');

     sa.set(n, S);

     return true;

 }

 int chk_clock = ;

 int vis[M];

 boolean check(int L, int R, int mid) {    // [L, R)

     if (R - L < K)

         return false;

     if (suf[sa[L]] - suf[sa[L] + mid])

         return false;

     chk_clock++;

     int rt = ;

     for (int i = L; i < R && rt < K; i++)

         if (vis[suf[sa[i]]] != chk_clock)

             vis[suf[sa[i]]] = chk_clock, rt++;

     return rt >= K;

 }

 boolean check(int mid) {

     int lst = ;

     boolean rt = false;

     for (int i = ; i < n && !rt; i++)

         if (sa(i) < mid)

             rt |= check(lst, i, mid), lst = i;

     if (!rt)

         rt |= check(lst, n, mid);

     return rt;

 }

 void output(int L, int R, int res) {

     if (!check(L, R, res))

         return;

     for (int i = sa[L], j = ; j < res; j++)

         putchar(S[i + j]);

     putchar('\n');

 }

 inline void solve() {

     chk_clock = ;

     memset(vis, , sizeof(vis));

     sa.build();

     sa.get_height();

     int l = , r = n / m, mid;

     while (l <= r) {

         mid = (l + r) >> ;

         if (check(mid))

             l = mid + ;

         else

             r = mid - ;

     }

     if (!(--l))

         puts("?");

     else {

         int lst = ;

         for (int i = ; i < n; i++)

             if (sa(i) < l)

                 output(lst, i, l), lst = i;

         output(lst, n, l);

     }

     puts("");

 }

 int main() {

     while (init())

         solve();

     return ;

 }