poj 3623(后缀数组)

poj 2774

poj 3623
字符串翻转后的和原串后的数组进行求后缀数组,然后之后两个指针$i,j$选择两端$rk$值最小的输出,注意格式

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
using namespace std;
const int MAXN = 30000 * 2 + 5;
int N, n, m, a[MAXN];
int SA[MAXN], rk[MAXN], tp[MAXN], tax[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(tp, rk), 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 init() {
char ch[10];
n = N;
for (int i=0;i<N;i++) {
scanf("%s", ch);
a[i] = ch[0];
}
a[n++] = '$';
for (int i=N-1;i>=0;i--) {
a[n++] = a[i];
}
a[n++] = 0;
m = 128;
}
void solve() {
build();
int i = 0, j = N+1, tot = 0;
do {
if (rk[i]<rk[j]) putchar(a[i]), i++, tot++;
else putchar(a[j]), j++, tot++;
if (tot%80==0) printf("\n");
} while (tot<N);
printf("\n");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &N)==1&&N) init(), solve();
return 0;
}

------ 本文结束 ------