###题目描述

你可能曾好奇为什么大多数外星生命形态都与人类相似，仅在一些表面特征上有所差异，比如身高、肤色、皱纹、耳朵、眉毛等。少数外星生命则与人类毫无相似之处，它们通常具有几何形状或无定形形态，如立方体、油膜或尘埃云。

答案在《星际迷航：下一代》第$146$集中揭晓，剧名为《The Chase》。原来在该象限的绝大多数生命形态中，最终都包含了一大段共同的$DNA$片段。

给定若干生命形态的$DNA$序列（由小写字母组成的字符串），你需要找到一个被其中超过半数生命形态共享的最长子串。

输入
标准输入包含多个测试用例。每个测试用例以$1 \leq n \leq 100$开头，表示生命形态的数量。随后是$n$行，每行包含一个由小写字母组成的字符串，表示一个生命形态的$DNA$序列。每个$DNA$序列的长度至少为$1$，且不超过$1000$。最后一个测试用例后跟一行$0$。

输出
对于每个测试用例，输出被超过半数生命形态共享的最长子串（可能有多个）。若有多个解，按字母序输出所有结果；如果没有至少包含一个字母的解，输出"?"。测试用例之间用空行分隔。

关键点说明：

1. 数字和公式标记：如$146$、$1 \leq n \leq 100$、$DNA$等已按需添加$符号。
2. 术语统一性：保持"DNA"大写，子串（substring）和字母序（alphabetical order）等术语准确。
3. 格式保留：输入输出格式与原文一致，包括空行分隔和"?"的特殊情况。
4. 文化背景：保留《星际迷航》剧集标题的英文原名（《The Chase》），避免直译。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;
#define ll long long
const int N = 300010;

int n, m, t;
char a[N];
int s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N], base[N], f[N][30], belong[N];
void get_sa()
{
	for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
	for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
	for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
	for (int k = 1; k <= n; k <<= 1)
	{
		int num = 0;
		for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
		for (int i = 1; i <= n; i ++ )
			if (sa[i] > k)
				y[ ++ num] = sa[i] - k;
		for (int i = 1; i <= m; i ++ ) c[i] = 0;
		for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
		for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
		for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
		swap(x, y);
		x[sa[1]] = 1, num = 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]) ? num : ++ num;
		if (num == n) break;
		m = num;
	}
}

void get_height()
{
	for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; i ++ )
	{
		if (rk[i] == 1) continue;
		if (k) k -- ;
		int j = sa[rk[i] - 1];
		while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
		height[rk[i]] = k;
	}
}

void init_rmq()
{
	base[0] = -1;
	for(int i = 1; i <= n; i ++)
	{
		f[i][0] = height[i];
		base[i] = base[i>>1] + 1;
	}
	for(int j = 1; j <= 18; j ++)
	{
		for(int i = 1; i + (1 << (j - 1)) <= n; i++)
		{
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
	}
}
int LCP(int x, int y) //第x和第y个后缀(不是排名)的最长公共前缀
{
	if(x == y) return n - x + 1;
	x = rk[x], y = rk[y];
	if(x > y) swap(x, y);
	x ++;
	int t = base[y - x + 1];
	return min(f[x][t], f[y - (1 << t) + 1][t]);
}
vector<int> pos[1010];
void init()
{
	for(int i = 0; i < 1010; i ++) pos[i].clear();
	memset(c, 0, sizeof c);
	memset(x, 0, sizeof x);
}
bool check(int mid)
{
	bool vis[110];
	memset(vis, 0, sizeof vis);
	int cnt = 0;
	bool ret = false, in = false;
	for(int i = 1; i <= n; i ++)
	{
		if(height[i] >= mid)
		{
			if(!vis[belong[sa[i]]]) vis[belong[sa[i]]] = 1, cnt ++;
			if(cnt > t / 2)
			{
				ret = true;
				if(!in)
				{
					in = true;
					pos[mid].push_back(sa[i]); // 第一次进入， 去重相同字符串
				}
			}
		}
		else
		{
			memset(vis, 0, sizeof vis);
			vis[belong[sa[i]]] = 1, cnt = 1, in = false;
		}
	}
	return ret;
}

int main()
{
	bool f = 0;
	while(scanf("%d", &t) && t)
	{
		if(f) printf("\n");
		else f = 1;
		init();
		n = 0;
		for(int i = 1; i <= t; i ++)
		{
			scanf("%s", a + 1);
			int len1 = strlen(a + 1);
			for(int j = 1; j <= len1; j ++)
			{
				s[++n] = a[j] - 'a' + 1;
				belong[n] = i;
			}
			s[++n] = 133 + i;
		}
		m = 300;
//		for(int i = 1; i <= n; i ++) cout << s[i];
//		cout << endl;
		get_sa();
		get_height();
		init_rmq();
//		for(int i = 1; i <= n; i ++)
//		{
//			for(int j = sa[i]; j <= n; j ++) cout << s[j] ;
//			cout << endl;
//		}
		int l = 0, r = 1000, ans = 0;
		while(l <= r)
		{
			int mid = l + r >> 1;
			if(check(mid))
			{
				ans = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		//cout << ans << endl;
		if(ans == 0) printf("?\n");
		else
		{ // 由于后缀数组性质, 就已经是
			for(unsigned int i = 0; i < pos[ans].size(); i ++)
			{
				for(int j = 0; j < ans; j ++)
				{
					printf("%c", s[pos[ans][i] + j] + 'a' - 1);
				}
				printf("\n");
			}
		}
	}
	return 0;
}