题意： 输入n个序列，求出一个最大长度的字符串，使得它在超过一半的DNA序列中连续出现。如果有多解，按照字典序从小到大输出所有解。
分析：这道题的关键是将多个字符串连接成一个串，方法是用不同的分隔符把所有原串拼接起来。接下来，就可以求这个新串的后缀数组和 height 数组， 然后二分答案，没次只需判断是非有一个长度为p的串在超过一半的串中出现过，判断方法是扫描一遍height数组，把它分成若干段，每当height[i] < p时，开辟一个新段，然后判断之前段是否包含了超过 n／2个原串后缀，那么当前的p值满足条件（注意n = 1时要特判）
详见代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std; const int maxn = ;
const int maxm = ;
char s[maxn*maxm];
int sa[maxn*maxm], t[maxn*maxm], t2[maxn*maxm], c[maxn*maxm]; int N;
void build_sa(int m) {
int* x = t, *y = t2;
for(int i = ; i < m; i++) c[i] = ;
for(int i = ; i < N; i++) c[x[i] = s[i]]++;
for(int i = ; i < m; i++) c[i] += c[i-];
for(int i = N-; i >= ; i--) sa[--c[x[i]]] = i;
for(int k = ; k <= N; k <<= ) {
int p = ;
for(int i = N-k; i < N; i++) y[p++] = i;
for(int i = ; i < N; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(int i = ; i < m; i++) c[i] = ;
for(int i = ; i < N; i++) c[x[y[i]]]++;
for(int i = ; i < m; i++) c[i] += c[i-];
for(int i = N-; i >= ; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = ;
x[sa[]] = ;
for(int i = ; i < N; i++)
x[sa[i]] = (y[sa[i-]] == y[sa[i]] && y[sa[i-]+k] == y[sa[i]+k] ? p- :p++);
if(p >= N) break;
m = p;
}
}
int rnk[maxn*maxm], height[maxn*maxm];
void get_height() {
int k = ;
for(int i = ; i < N; i++) rnk[sa[i]] = i;
for(int i = ; i < N; i++) {
if(!rnk[i]) continue;
int j = sa[rnk[i]-];
if(k) k--;
while(s[i+k] == s[j+k]) k++;
height[rnk[i]] = k;
}
} int n;
char s2[maxm];
int sign[maxn];
int mlen;
vector<int> A;
int flag[maxn];
map<char, int> Map;
bool find(int p, vector<int> &A) { //判断当前长度p是否符合要求
memset(flag, , sizeof flag);
bool OK = false;
int cnt = ;
int start = ;
int t = lower_bound(sign, sign+n, sa[start]) - sign;
if(!Map.count(s[sa[start]]))
cnt++;
flag[t] = start;
for(int i = ; i < N; i++) {
if(height[i] >= p) {
t = lower_bound(sign, sign+n, sa[i]) - sign;
if(!Map.count(s[sa[i]]) && flag[t] < start)
cnt++;
flag[t] = i;
if(i == N- && cnt > n/){
OK = true;
A.push_back(sa[start]);
}
}
else {
if(cnt > n/) {
OK = true;
A.push_back(sa[start]);
}
cnt = ;
start = i;
int t = lower_bound(sign, sign+n, sa[start]) - sign;
if(!Map.count(s[sa[start]]))
cnt++;
flag[t] = start;
}
}
return OK;
}
int cnt;
char gen_sign() { //生成分隔符并记录
int i = ;
for(; i < ; i++) if(!Map.count(i) && (i < 'a' || i > 'z')) break;
Map[i] = ++cnt;
return i;
}
int main() {
int tt = ;
while(scanf("%d", &n) == && n) {
if(tt++) puts("");
if(n == ) {
scanf("%s", s);
printf("%s\n", s);
continue;
}
cnt = ;
Map.clear();
N = ;
for(int i = ; i < n; i++) {
scanf("%s", s2);
strcpy(s+N, s2);
N += strlen(s2);
s[N++] = gen_sign();
sign[i] = N-;
}
s[N] = '\0';
//cout << s <<endl;
//for(int i = 0; i < n; i++) cout<< sign[i] <<endl;
build_sa();
get_height();
//for(int i = 0; i < N; i++) printf("%d ", sa[i]);
//puts("");
//for(int i = 0; i < N; i++) printf("%d ", height[i]);
//puts("");
mlen = ;
int L = , R = N-;
A.clear();
vector<int> B;
while(R >= L) {
int M = L + (R-L+)/;
B.clear();
if(find(M, B)) {
mlen = M;
A = B;
L = M+;
}
else R = M-;
} if(A.size() == ) printf("?\n");
for(int i = ; i < A.size(); i++) {
for(int j = ; j < mlen; j++) printf("%c", s[A[i]+j]);
printf("\n");
}
}
}