用奇怪的字符把它们连接起来。然后求sa，hei，二分答案，按mid分组。
判断每一组存在的后缀属于的原串的种类数是不是存在那么多个。
这个做法可以推广到多串求LCS，然后多个log，完美在SPOJ上T掉。
Code
/**
* 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 ;
}