1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
const int N = 800010, M = 4010;
int n, T;
int sa[N], rk[N], cnt[N], oldrk[N << 1], id[N], px[N];
char s[N];
int ht[N];
int belong[N], idx;
int maxr = N;
inline bool cmp(int x, int y, int k) {
return oldrk[x] == oldrk[y] && oldrk[x + k] == oldrk[y + k];
}
void SA() {
int i, p = 0, k, m = 300;
memset(cnt, 0, sizeof cnt);
for (i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
for (k = 1; k < n; k <<= 1, m = p) {
for (p = 0, i = n ; i > n - k; i--) id[++p] = i;
for (i = 1;i <= n; i++){
if (sa[i] > k) id[++p] = sa[i] - k;
}
memset(cnt, 0, sizeof cnt);
for (i = 1; i <= n; i++) cnt[px[i] = rk[id[i]]]++;
for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; i--) sa[cnt[px[i]]--] = id[i];
memcpy(oldrk, rk, sizeof rk);
for (p = 0, i = 1; i <= n; i++){
rk[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
}
}
for (int i = 1; i <= n; i++) {
if (rk[i] == 1) continue;
int k = max(ht[rk[i - 1]] - 1, 0);
while (i + k <= n && s[i + k]== s[sa[rk[i] - 1] + k]) k++;
ht[rk[i]] = k;
}
}
bool check(int len) {
set<int> S;
S.insert(belong[sa[1]]);
for (int i = 2; i <= n; i++) {
while (ht[i] >= len && i <= n) {
S.insert(belong[sa[i]]);
i++;
}
if (S.size() == T) return true;
S.clear();
S.insert(belong[sa[i]]);
}
return false;
}
void print(int len) {
set<int> S;
bool flag = false;
S.insert(belong[sa[1]]);
for (int i = 2; i <= n; i++) {
while (ht[i] >= len && i <= n) {
S.insert(belong[sa[i]]);
i++;
}
if (S.size() == T) {
for (int j = sa[i - 1]; j <= sa[i - 1] + len - 1; j++) putchar(s[j]);
puts("");
flag = true;
break;
}
S.clear();
S.insert(belong[sa[i]]);
}
if (!flag) puts("IDENTITY LOST");
}
void solve() {
maxr = N;
char a = 1;
memset(belong, -1, sizeof belong);
idx = 0;
int t = 0;
for (int i = 0; i < T; i++) {
scanf("%s", s + t + 1);
int m = strlen(s + 1);
maxr = min(maxr, m - t);
s[m + 1] = a++;
if (a == 97) a = 1;
for (int j = t + 1; s[j]; j++) belong[j] = i;
t = m + 1;
}
s[t] = '\0';
// printf("%s\n", s + 1);
// for (int i = 1; s[i]; i++) printf("%d ", belong[i]);
n = strlen(s + 1);
SA();
// 二分LCP的长度
int l = 1, r = maxr;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
print(l);
}
int main() {
while (scanf("%d", &T), T) solve();
return 0;
}
|