POJ上的，ZOJ上的OJ的最长回文子串数据量太大，用后缀数组的方法非常吃力，所以只能挑个数据量小点的试下，真要做可能还是得用manacher。贴一下代码
两个小错，一个是没弄懂string类的substr的用法是S.substr(i,len)从i开始的长度为len的一段。另外一个是RMQ的时候，询问rk[i],rk[j]的最长前缀应该是等效于求lcp[rk[i]] lcp[rk[j]-1]这一段，这个要在询问的时候注意一下。
|
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
123
124
125
126
127
128
129
130
131
|
#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>#include<vector>#include<cmath>#define maxn 1000050using
namespace std;
int
sa[maxn + 50];
int
lcp[maxn + 50];
int
rk[maxn + 50];
int
tmp[maxn + 50];
int
d[maxn + 50][25];
int
n, k;
bool
cmp_sa(int
i, int
j)
{ if
(rk[i] != rk[j]) return
rk[i] < rk[j];
else{
int
ri = i + k <= n ? rk[i + k] : -1;
int
rj = j + k <= n ? rk[j + k] : -1;
return
ri < rj;
}
}void
construct_sa(string S, int
*sa)
{ n = S.length();
for
(int i = 0; i <= n; i++){
sa[i] = i;
rk[i] = i < n ? S[i] : -1;
}
for
(k = 1; k <= n; k <<= 1){
sort(sa, sa + n + 1, cmp_sa);
tmp[sa[0]] = 0;
for
(int i = 1; i <= n; i++){
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for
(int i = 0; i <= n; i++){
rk[i] = tmp[i];
}
}
}void
construct_lcp(string S, int
*sa, int
*lcp)
{ n = S.length();
for
(int i = 0; i <= n; i++) rk[sa[i]] = i;
int
h = 0;
lcp[0] = 0;
for
(int i = 0; i < n; i++){
int
j = sa[rk[i] - 1];
for
(h ? h-- : 0; i + h < n&&j + h < n&&S[i + h] == S[j + h]; h++);
lcp[rk[i] - 1] = h;
}
}void
construct_rmq(int
*lcp,int
sizen)
{ for
(int i = 0; i <= sizen; i++) d[i][0] = lcp[i];
for
(int j = 1; (1 << j) <= sizen; j++){
for
(int i = 0; (i + (1 << j) - 1) <= sizen; i++){
d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
}
}int
rmq_query(int
l, int
r)
{ if
(l > r) swap(l, r); r -= 1;
int
k = 0; int
len = r - l + 1;
while
( (1 << (k + 1)) < len) k++;
return
min(d[l][k], d[r - (1 << k) + 1][k]);
}string S;string T;int
main()
{ int
ca = 0;
while
(cin >> S)
{
if
(S == "END") break;
int
ctr = S.length();
T = S;
reverse(T.begin(), T.end());
S += ‘#‘
+ T;
construct_sa(S, sa);
construct_lcp(S, sa, lcp);
construct_rmq(lcp, S.length() + 1);
int
ans = 0;
string ansString;
int
ansid;
int
anstype;
for
(int i = 0; i < ctr; i++){
int
j = 2 * ctr - i;
int
l = rmq_query(rk[i], rk[j]);
if
(2 * l - 1>ans){
ans = 2 * l - 1;
ansid = i;
anstype = 0;
}
}
for
(int i = 1; i < ctr; i++){
int
j = 2 * ctr - i + 1;
int
l = rmq_query(rk[i], rk[j]);
if
(2 * l > ans){
ansid = i;
anstype = 1;
ans = 2 * l;
}
}
if
(anstype == 0){
//ansString = S.substr(ansid-(ans-1)/2, ansid + (ans - 1) / 2);
for
(int i = ansid - (ans - 1) / 2; i <= ansid + (ans - 1) / 2; i++){
cout << S[i];
}
cout << endl;
}
else{
//ansString = S.substr(ansid - ans / 2, ansid + ans / 2);
for
(int i = ansid - ans/ 2; i <= ansid + ans/ 2-1; i++){
cout << S[i];
}
cout << endl;
}
}
return
0;
} |