#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
const int base = 37;
const int mod = 1e9 + 7;
int n;
string s;
int sa[maxn], pos[maxn], pw[maxn], hsh[maxn], rev[maxn], lmq[19][maxn], rmq[19][maxn];
ll answer;
vector<int> seg[4 * maxn];
int get_rev(int L, int R){
ll ret = rev[L] - 1ll * rev[R + 1] * pw[R - L + 1] % mod;
if (ret < 0)
ret += mod;
return ret;
}
int get_hsh(int L, int R){
if (L == 0)
return hsh[R];
ll ret = hsh[R] - 1ll * hsh[L - 1] * pw[R - L + 1] % mod;
if (ret < 0)
ret += mod;
return ret;
}
/*
int lcp(int fi, int se){
if (fi == se)
return n - fi;
fi = pos[fi], se = pos[se];
if (fi > se)
swap(fi, se);
int len = se - fi;
len = log2(len);
return min(rmq[len][fi], lmq[len][se]);
}*/
int lcp(int fi, int se){
int lo = 0, hi = min(n - fi + 1, n - se + 1);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(fi, fi + mid - 1) == get_hsh(se, se + mid - 1))
lo = mid;
else
hi = mid;
}
return lo;
}
bool cmp(int fi, int se){
int lo = 0, hi = min(n - fi + 1, n - se + 1);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(fi, fi + mid - 1) == get_hsh(se, se + mid - 1))
lo = mid;
else
hi = mid;
}
if (lo == n - fi or (lo < n - se and s[fi + lo] < s[se + lo]))
return 1;
return 0;
}
void buildSA(){
for (int i = 0; i < n; i++)
sa[i] = i;
sort(sa, sa + n, cmp);
for (int i = 0; i < n; i++)
pos[sa[i]] = i;
/* memset(rmq, 63, sizeof rmq);
memset(lmq, 63, sizeof lmq);
for (int i = 0; i < n - 1; i++){
int tmp = lcp(sa[i], sa[i + 1]);
rmq[0][i] = tmp;
lmq[0][i + 1] = tmp;
}
for (int i = 0; i < 18; i++)
for (int j = 0; j + (1 << i) < n; j++)
rmq[i + 1][j] = min(rmq[i][j], rmq[i][j + (1 << i)]);
for (int i = 0; i < 18; i++)
for (int j = n - 1; j - (1 << i) >= 0; j--)
lmq[i + 1][j] = min(lmq[i][j], lmq[i][j - (1 << i)]);
*/
}
void check(int L, int R){
int len = R - L + 1;
int fi, se;
int lo = -1, hi = pos[L];
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (lcp(L, sa[mid]) >= len)
hi = mid;
else
lo = mid;
}
fi = hi;
lo = pos[L], hi = n;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (lcp(L, sa[mid]) >= len)
lo = mid;
else
hi = mid;
}
se = lo;
answer = max(answer, 1ll * len * (se - fi + 1));
}
void get(int id, int L, int R, int idx, int len){
for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
int t = -seg[id][i];
t --;
t = (t - idx + 1);
if (2 * t <= len)
break;
check(idx, idx + 2 * t - 1);
}
for (int i = (int)(seg[id].size()) - 1; i >= 0 and seg[id][i] > 0; i--){
int t = seg[id][i];
t --;
t = (t - idx);
if (2 * t + 1 <= len)
break;
check(idx, idx + 2 * t);
}
if (L + 1 == R)
return;
int mid = (L + R) >> 1;
if (idx < mid)
get(2 * id + 0, L, mid, idx, len);
else
get(2 * id + 1, mid, R, idx, len);
}
void add(int id, int L, int R, int l, int r, int x){
if (L == l and R == r){
seg[id].push_back(x);
return;
}
int mid = (L + R) >> 1;
if (l < mid)
add(2 * id + 0, L, mid, l, min(mid, r), x);
if (mid < r)
add(2 * id + 1, mid, R, max(l, mid), r, x);
}
int main(){
ios_base::sync_with_stdio(false);
cin >> s;
n = s.size();
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = 1ll * pw[i - 1] * base % mod;
for (int i = 0; i < n; i++){
if (i == 0)
hsh[i] = (int)(s[i] - 'a' + 1);
else
hsh[i] = (1ll * hsh[i - 1] * base + (int)(s[i] - 'a' + 1)) % mod;
}
for (int i = n - 1; i >= 0; i--)
rev[i] = (1ll * rev[i + 1] * base + (int)(s[i] - 'a' + 1)) % mod;
buildSA();
for (int i = 0; i < n; i++){
int lo = 0, hi = min(i, n - i - 1) + 1;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(i - mid, i - 1) == get_rev(i + 1, i + mid))
lo = mid;
else
hi = mid;
}
add(1, 0, n, i - lo, i + 1, i + 1);
if (i < n - 1){
lo = 0, hi = min(i + 2, n - i);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(i - mid + 1, i) == get_rev(i + 1, i + mid))
lo = mid;
else
hi = mid;
}
if (lo > 0)
add(1, 0, n, i - lo + 1, i + 1, -(i+1));
}
}
for (int i = 1; i < 4 * maxn; i++)
sort(seg[i].begin(), seg[i].end());
for (int i = 0; i < n; i++){
int idx = sa[i];
int len = 0;
if (i > 0)
len = lcp(sa[i], sa[i - 1]);
get(1, 0, n, idx, len);
}
cout << answer << endl;
}
Compilation message
palindrome.cpp: In function 'void get(int, int, int, int, int)':
palindrome.cpp:119:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
28544 KB |
Output is correct |
2 |
Correct |
32 ms |
28544 KB |
Output is correct |
3 |
Correct |
31 ms |
28544 KB |
Output is correct |
4 |
Correct |
35 ms |
28536 KB |
Output is correct |
5 |
Correct |
35 ms |
28544 KB |
Output is correct |
6 |
Correct |
33 ms |
28536 KB |
Output is correct |
7 |
Correct |
29 ms |
28544 KB |
Output is correct |
8 |
Correct |
35 ms |
28544 KB |
Output is correct |
9 |
Correct |
35 ms |
28536 KB |
Output is correct |
10 |
Correct |
36 ms |
28536 KB |
Output is correct |
11 |
Correct |
35 ms |
28536 KB |
Output is correct |
12 |
Correct |
34 ms |
28544 KB |
Output is correct |
13 |
Correct |
33 ms |
28544 KB |
Output is correct |
14 |
Correct |
38 ms |
28544 KB |
Output is correct |
15 |
Correct |
32 ms |
28544 KB |
Output is correct |
16 |
Correct |
31 ms |
28544 KB |
Output is correct |
17 |
Correct |
37 ms |
28544 KB |
Output is correct |
18 |
Correct |
34 ms |
28536 KB |
Output is correct |
19 |
Correct |
36 ms |
28544 KB |
Output is correct |
20 |
Correct |
36 ms |
28544 KB |
Output is correct |
21 |
Correct |
40 ms |
28536 KB |
Output is correct |
22 |
Correct |
36 ms |
28580 KB |
Output is correct |
23 |
Correct |
36 ms |
28536 KB |
Output is correct |
24 |
Correct |
34 ms |
28544 KB |
Output is correct |
25 |
Correct |
29 ms |
28576 KB |
Output is correct |
26 |
Correct |
30 ms |
28544 KB |
Output is correct |
27 |
Correct |
34 ms |
28544 KB |
Output is correct |
28 |
Correct |
34 ms |
28540 KB |
Output is correct |
29 |
Correct |
31 ms |
28516 KB |
Output is correct |
30 |
Correct |
38 ms |
28544 KB |
Output is correct |
31 |
Correct |
38 ms |
28544 KB |
Output is correct |
32 |
Correct |
36 ms |
28516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
28768 KB |
Output is correct |
2 |
Correct |
34 ms |
28672 KB |
Output is correct |
3 |
Correct |
43 ms |
28664 KB |
Output is correct |
4 |
Correct |
40 ms |
28700 KB |
Output is correct |
5 |
Correct |
39 ms |
28664 KB |
Output is correct |
6 |
Correct |
39 ms |
28696 KB |
Output is correct |
7 |
Correct |
42 ms |
28616 KB |
Output is correct |
8 |
Correct |
40 ms |
28660 KB |
Output is correct |
9 |
Correct |
36 ms |
28660 KB |
Output is correct |
10 |
Correct |
35 ms |
28544 KB |
Output is correct |
11 |
Correct |
37 ms |
28672 KB |
Output is correct |
12 |
Correct |
36 ms |
28664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
29752 KB |
Output is correct |
2 |
Correct |
124 ms |
29816 KB |
Output is correct |
3 |
Correct |
118 ms |
30280 KB |
Output is correct |
4 |
Correct |
154 ms |
30340 KB |
Output is correct |
5 |
Correct |
112 ms |
29176 KB |
Output is correct |
6 |
Correct |
117 ms |
29368 KB |
Output is correct |
7 |
Correct |
113 ms |
29688 KB |
Output is correct |
8 |
Correct |
78 ms |
29236 KB |
Output is correct |
9 |
Correct |
71 ms |
29068 KB |
Output is correct |
10 |
Correct |
111 ms |
29296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1065 ms |
39936 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1074 ms |
33672 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |