思路：
后缀数组+二分：
我们先把n 个字符串用不同的字符连接起来，注意最后要加上一个字符。
然后求这个字符串的后缀数组。
然后二分答案，判断长度len 是否可行。 判断方法是同样的套路，给sa数组进行分块，每一块都大于等于长度len，然后判断每一块是否有超过一半的串在这一块中出现， 可以开一个flag数组， 记录每一块的字符串， 最后统计flag数组即可。
这样我们二分得到了最长长度len。
然后打印解。
同样的方式 枚举每一块，如果这一块合法， 因为这一块每一个字符串 前len 个字符都是一样的， 直接取前len个字符就是答案。
最后排序即可。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <string> #define Siz(x) (int)x.size() using namespace std; const int maxn = 1000000 + 10; int t1[maxn], t2[maxn], c[maxn]; bool cmp(int* r, int a,int b,int l){ return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int str[], int sa[], int Rank[], int lcp[], int n, int m){ ++n; int i, j, p, *x = t1, *y = t2; for (i = 0; i < m; ++i) c[i] = 0; // puts("hha"); for (i = 0; i < n; ++i) c[x[i] = str[i] ]++; for (i = 1; i < m; ++i) c[i] += c[i-1]; for (i = n-1; i >= 0; --i) sa[--c[x[i] ] ] = i; for (j = 1; j <= n; j <<= 1){ p = 0; for (i = n-j; i < n; ++i) y[p++] = i; for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; for (i = 0; i < m; ++i) c[i] = 0; for (i = 0; i < n; ++i) c[x[y[i] ] ]++; for (i = 1; i < m; ++i) c[i] += c[i-1]; for (i = n-1; i >= 0; --i) sa[--c[x[y[i] ] ] ] = y[i]; swap(x,y); p = 1; x[sa[0] ] = 0; for (i = 1; i < n; ++i){ x[sa[i] ] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++; } if (p >= n)break; m= p; } int k = 0; n--; for (i = 0; i <= n; ++i) Rank[sa[i] ] = i; for (i = 0; i < n; ++i){ if (k)--k; j = sa[Rank[i]-1 ]; while(str[i+k] == str[j+k])++k; lcp[Rank[i] ] = k; } } int lcp[maxn], a[maxn], sa[maxn], Rank[maxn]; int n,k; char s[1000 + 10]; vector<int>bit; int cnt, id; int flag[100 + 10]; int nn; bool judge(int m){ int cp = n / 2; bit.clear(); bit.push_back(sa[1]); for (int i = 2; i <= cnt; ++i){ if (lcp[i] >= m) bit.push_back(sa[i]); else { memset(flag,0,sizeof flag); for (int j = 0; j < Siz(bit); ++j){ int v = bit[j] / (nn+1); flag[v] = 1; } int sum = 0; for (int j = 0; j < n; ++j) sum += flag[j]; if (sum > cp) return true; bit.clear(); bit.push_back(sa[i]); } } memset(flag,0,sizeof flag); for (int j = 0; j < Siz(bit); ++j){ int v = bit[j] / (nn+1); flag[v] = 1; } int sum = 0; for (int j = 0; j < n; ++j) sum += flag[j]; if (sum > cp) return true; return false; } int ks = 0; vector<string>Vec; void solve(int len){ if (len == 0){ puts("?"); return; } int cp = n / 2; bit.clear(); bit.push_back(sa[1]); for (int i = 2; i <= cnt; ++i){ if (lcp[i] >= len) bit.push_back(sa[i]); else { string tmp; for (int j = bit[0], k= 0; k < len; ++k, ++j) { tmp += a[j] - 1 + 'a'; } int kk = Siz(bit); memset(flag,0,sizeof flag); for (int j = 0; j < Siz(bit); ++j){ int v = bit[j] / (nn+1); flag[v] = 1; } int sum = 0; for (int j = 0; j < n; ++j) sum += flag[j]; if (sum > cp){ string ans; for (int i = bit[0], j = 0; j < len; ++j,++i){ char ch = a[i]-1+'a'; ans += ch; } Vec.push_back(ans); } bit.clear(); bit.push_back(sa[i]); } } memset(flag,0,sizeof flag); for (int j = 0; j < Siz(bit); ++j){ int v = bit[j] / (nn+1); flag[v] = 1; } int sum = 0; for (int j = 0; j < n; ++j) sum += flag[j]; if (sum > cp){ string ans; for (int i = bit[0], j = 0; j < len; ++j,++i){ char ch = a[i]-1+'a'; ans += ch; } Vec.push_back(ans); } } int main(){ while(~scanf("%d",&n) && n){ Vec.clear(); id=26, cnt = 0; int len; for (int i = 0; i < n; ++i){ scanf("%s",s); if (i == 0) nn = strlen(s); for (int j = 0; s[j] ;++j){ a[cnt++] = s[j] - 'a' + 1; } a[cnt++] = ++id; } a[cnt] = 0; da(a, sa, Rank, lcp, cnt, 200); int l = 1, r = cnt, m; while(l <= r){ m = l + r >> 1; if (judge(m)) l = m + 1; else r = m - 1; } if (ks++) putchar('\n'); solve(r); sort(Vec.begin(), Vec.end()); for (int i = 0; i < Siz(Vec); ++i){ printf("%s\n", Vec[i].c_str()); } } return 0; }