生命形式
| 时间限制： 5000MS | 内存限制： 65536K | |
| 提交总数： 16660 | 接受： 4910 |
描述
你可能想知道为什么大多数外星人的生命形式与人类相似，不同的是表面特征，如身高，肤色，皱纹，耳朵，眉毛等等。有几个没有人类的相似之处; 这些通常具有几何形状或无定形形状，如立方体，浮油或灰尘云。
“ 星际迷航 ”第146集“ The Chase ” 给出了答案。事实证明，在这个象限的绝大多数生命形式中，共同DNA的一大片段结束了。
考虑到以字母串表示的几种生命形式的DNA序列，你应该找到一半以上的共享时间最长的子串。
输入
标准输入包含几个测试用例。每个测试用例始于1≤ Ñ ≤100，生命形式的数目。n行跟随; 每个都包含一串小写字母，代表生命形式的DNA序列。每个DNA序列包含至少一个但不超过1000个字母。最后一个测试用例后面是一行。
产量
对于每个测试用例，输出一半以上生命形式共享的最长的字符串或字符串。如果有多个，按字母顺序输出。如果至少有一个字母没有解决方案，输出“？”。在测试用例之间留下一条空行。
示例输入
3 ABCDEFG bcdefgh cdefghi 3 XXX YYY ZZZ 0
示例输出
bcdefg cdefgh ？
类似双串匹配，我们将所有串通过一个间隔符链接起来，但要注意使用不同的间隔符，否则可能会将间隔符加入匹配【与双串不同，因为双串只有一个间隔符，无论如何也不会参与匹配】
之后我们常规二分答案，对于给定长度len，看看能否找到连续height都>=len且出现过的串的个数 >= N/2
最后我们得到ans，再进行一次查询，这次一找到直接输出
方法还是很直白，~~只是要考虑特判N = 1~~【不然会全部输出，直接OLE QAQ】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100200,maxm = 100005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
char s[maxn],A[maxn];
int sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],c[maxn],n,m,N,vis[105];
int id[maxn],len[maxn],Max;
void SA(){
int *x = t1,*y = t2;
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1){
int p = 0;
for (int i = n - k + 1; i <= n; i++) y[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k;
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[y[i]]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
swap(x,y);
p = 1; x[sa[1]] = 1;
for (int i = 2; i <= n; i++)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
if (p >= n) break;
m = p;
}
for (int i = 1; i <= n; i++) rank[sa[i]] = i;
int k = 0;
for (int i = 1; i <= n; i++){
if (k) k--;
int j = sa[rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
height[rank[i]] = k;
}
}
bool check(int K){
memset(vis,-1,sizeof(vis));
int flag = 0,cnt = 0;
for (int i = 1; i <= n; i++){
if (id[sa[i]] == -1){flag++; cnt = 1; continue;}
if (height[i] < K) cnt = 1,vis[id[sa[i]]] = ++flag;
else {if (vis[id[sa[i]]] != flag) ++cnt; vis[id[sa[i]]] = flag;}
if (cnt > N / 2) return true;
}
return false;
}
void getans(int K){
//cout<<K<<endl;
memset(vis,-1,sizeof(vis));
int flag = 0,cnt = 0,pos = sa[1],ok = true;
for (int i = 1; i <= n; i++){
if (id[sa[i]] == -1){flag++; cnt = 1; ok = true; pos = sa[i]; continue;}
if (height[i] < K) cnt = 1,vis[id[sa[i]]] = ++flag,ok = true,pos = sa[i];
else {if (vis[id[sa[i]]] != flag) ++cnt; vis[id[sa[i]]] = flag;}
if (cnt * 2 > N && ok){
ok = false;
for (int j = 0; j < K; j++) putchar(s[pos + j]);
puts("");
}
}
}
void solve(){
int l = 0,r = Max,mid;
while (l < r){
mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
if (!l) printf("?
");
else getans(l);
printf("
");
}
int main(){
while ((N = RD())){
if (N == 1){
scanf("%s",s + 1);
printf("%s
",s + 1);
continue;
}
s[1] = ' '; n = 0; m = 256; Max = -INF;
int tem,C = 0;
REP(i,N){
scanf("%s",A); tem = strlen(A); len[i] = n + tem; Max = max(Max,tem);
for (int j = 1; j <= tem; j++) id[n + j] = i; id[n + tem + 1] = -1;
strcat(s + 1,A); A[0] = ++C; A[1] = ' '; strcat(s + 1,A);
n += tem + 1;
}
//REP(i,n) cout<<id[i];cout<<endl;
SA();
//for (int i = 2; i <= n; i++) cout<<height[i]<<' ';cout<<endl;
solve();
}
return 0;
}