poj 3294(二分+后缀数组)

poj 3294

这题差不多,二分后后缀数组$height$判断,此题要输出所有的解,用个数组存下每个解在$a$中的起始位置即可。不同的是,此题判断时一定要找到一个$height[i]<x$或者循环完毕$height$才能更新解,这样才能防止重复解出现。
(ps: $vi$数组不要开大了,否则memset时容易TLE)

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
119
120
121
122
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj3296"
using namespace std;
const int MAXN = 105 * 1005 + 5;
char s[MAXN];
int ans,ba,bf[MAXN],mini,t,n,m,a[MAXN],tp[MAXN],SA[MAXN],rk[MAXN],tax[MAXN],height[MAXN],belong[MAXN];
bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];}
void build() {
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;
int p;
for (int k=1;k<=n;k*=2) {
p = 0;
for (int i=n-k;i<n;i++) tp[p++] = i;
for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[tp[i]]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];
swap(rk, tp), p = 0, rk[SA[0]] = 0;
for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
if (++p>=n) break;
m = p;
}
}
void getH() {
int k = 0;
for (int i=0;i<n;i++) {
if (k) k--;
int j = SA[rk[i]-1];
while (a[i+k]==a[j+k]) k++;
height[rk[i]] = k;
}
}
void init() {
n = 0, m = 200, mini = 200000000;
for (int i=0;i<t;i++) {
scanf("%s", s);
int l = strlen(s);
mini = min(mini, l);
for (int j=0;j<l;j++) belong[n] = i, a[n++] = s[j];
belong[n] = 104; a[n++] = m++;
}
a[n-1] = 0, m+=5;
}
int vi[100 + 5];
bool check(int x) {
int tot = 0, flag = false;
ms(vi, false);
for (int i=2;i<n;i++) {
if (height[i]<x) {
if (tot>t/2) {
flag = true;
if (x>ba) {
ans = 0;
ba = x;
bf[ans] = SA[i-1];
ans++;
} else if (x==ba) {
bf[ans] = SA[i-1];
ans++;
}
}
ms(vi, false);
tot = 0;
continue;
}
if (!vi[belong[SA[i]]]) vi[belong[SA[i]]] = true, ++tot;
if (!vi[belong[SA[i-1]]]) vi[belong[SA[i-1]]] = true, ++tot;
}
if (tot>t/2) {
if (x>ba) {
ans = 0;
ba = x;
bf[ans] = SA[n-1];
ans++;
} else if (x==ba) {
bf[ans] = SA[n-1];
ans++;
}
return true;
}
return flag;
}
void solve() {
build(), getH();
int l = 1, r = mini + 1;
ba = 0, ms(bf, 0), ans = 0;
while (l<r) {
int mid = (l+r)/2;
if (check(mid)) {
l = mid + 1;
} else r = mid;
}
if (!ans) printf("?\n"); else {
for (int i=0;i<ans;i++) {
for (int j=bf[i];j<bf[i]+ba;j++) {
printf("%c", a[j]);
}
printf("\n");
}
}
printf("\n");
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen("1.out","w",stdout);
#endif
while(scanf("%d", &t)==1&&t) init(), solve();
return 0;
}
------ 本文结束 ------