#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
string s;
int n, m;
int pos[2 * maxn], suf[2 * maxn], tmp[2 * maxn], parsum[2 * maxn];
int gap;
ll answer = 0;
bool sufCmp(int i, int j){
if (pos[i] != pos[j])
return pos[i] < pos[j];
i += gap, j += gap;
return (i < m && j < m) ? pos[i] < pos[j] : i > j;
}
void buildSA(){
m = s.size();
for (int i = 0; i < m; i++){
suf[i] = i;
pos[i] = (int)(s[i] - 'a');
}
for (gap = 1; ; gap += gap){
sort(suf, suf + m, sufCmp);
for (int j = 1; j < m; j++)
tmp[j] = tmp[j - 1] + sufCmp(suf[j - 1], suf[j]);
for (int j = 0; j < m; j++)
pos[suf[j]] = tmp[j];
if (tmp[m - 1] == m - 1)
break;
}
for (int i = 0; i < m; i++)
parsum[i] = (suf[i] < n) + ((i > 0) ? parsum[i - 1] : 0);
}
int rcp[20][maxn], lcp[20][maxn];
void buildLCP(){
memset(lcp, 63, sizeof lcp);
memset(rcp, 63, sizeof rcp);
for (int i = 0, k = 0; i < m; i++){
if (pos[i] != m - 1){
for (int j = suf[pos[i] + 1]; s[i + k] == s[j + k];)
k ++;
lcp[0][pos[i] + 1] = k;
rcp[0][pos[i] + 0] = k;
if (k > 0)
k --;
}
}
for (int i = 0; i < 19; i++)
for (int j = 0; j + (1 << i) < m; j++)
rcp[i + 1][j] = min(rcp[i][j], rcp[i][j + (1 << i)]);
for (int i = 0; i < 19; i++)
for (int j = m - 1; j - (1 << i) >= 0; j--)
lcp[i + 1][j] = min(lcp[i][j], lcp[i][j - (1 << i)]);
}
int get_lcp(int i, int j){
if (i == j)
return m - i;
if (i > j)
swap(i, j);
int len = log2(j - i);
return min(rcp[len][i], lcp[len][j]);
}
vector<int> seg[4 * maxn];
void check(int lef, int rig){
int L, R;
int len = rig - lef + 1;
int idx = pos[lef];
for (int i = 19; i >= 0; i--)
if (idx - (1 << i) >= 0 and lcp[i][idx] >= len)
idx -= (1 << i);
L = idx;
idx = pos[lef];
for (int i = 19; i >= 0; i--)
if (idx + (1 << i) < m and rcp[i][idx] >= len)
idx += (1 << i);
R = idx;
int num = parsum[R] - (L > 0 ? parsum[L - 1] : 0);
answer = max(answer, 1ll * num * len);
}
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] - 1;
if (2 * (t - idx + 1) <= len)
break;
check(idx, idx + 2 * (t - idx + 1) - 1);
}
for (int i = (int)seg[id].size() - 1; i >= 0 and seg[id][i] > 0; i++){
int t = seg[id][i] - 1;
if (2 * (t - idx) + 1 <= len)
break;
check(idx, idx + 2 * (t - idx));
}
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 idx){
if (L == l and R == r){
seg[id].push_back(idx);
return;
}
int mid = (L + R) >> 1;
if (l < mid)
add(2 * id + 0, L, mid, l, min(mid, r), idx);
if (mid < r)
add(2 * id + 1, mid, R, max(l, mid), r, idx);
}
int main(){
ios_base::sync_with_stdio(false);
cin >> s;
n = s.size();
string obj = s + "#";
reverse(s.begin(), s.end());
obj += s;
s = obj;
buildSA();
buildLCP();
for (int i = 0; i < n; i++){
int lo = 0, hi = min(i + 1, n - i);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_lcp(pos[i - mid], pos[(1 + n) + (n - i - mid - 1)]) >= mid)
lo = mid;
else
hi = mid;
}
add(1, 0, n, i - lo, i + 1, +(i + 1));
lo = 0, hi = min(i + 2, n - i);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_lcp(pos[i - mid + 1], pos[(1 + n) + (n - i - mid - 1)]) >= mid)
lo = mid;
else
hi = mid;
}
if (lo > 0)
add(1, 0, n, i - lo + 1, i + 1, -(i + 1));
}
for (int i = 0; i < 4 * maxn; i++)
sort(seg[i].begin(), seg[i].end());
int last = -1, len = 0;
for (int i = 0; i < m; i++){
if (suf[i] >= n)
continue;
if (last != -1){
len = get_lcp(pos[suf[i]], pos[last]);
last = suf[i];
}
get(1, 0, n, suf[i], len);
}
cout << answer << endl;
}
Compilation message
palindrome.cpp: In function 'void get(int, int, int, int, int)':
palindrome.cpp:93: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 |
68 ms |
75448 KB |
Output is correct |
| 2 |
Correct |
77 ms |
75476 KB |
Output is correct |
| 3 |
Correct |
76 ms |
75512 KB |
Output is correct |
| 4 |
Correct |
73 ms |
75516 KB |
Output is correct |
| 5 |
Correct |
68 ms |
75512 KB |
Output is correct |
| 6 |
Correct |
67 ms |
75512 KB |
Output is correct |
| 7 |
Correct |
66 ms |
75512 KB |
Output is correct |
| 8 |
Correct |
66 ms |
75640 KB |
Output is correct |
| 9 |
Correct |
67 ms |
75640 KB |
Output is correct |
| 10 |
Correct |
71 ms |
75768 KB |
Output is correct |
| 11 |
Correct |
69 ms |
75464 KB |
Output is correct |
| 12 |
Correct |
66 ms |
75512 KB |
Output is correct |
| 13 |
Incorrect |
73 ms |
75612 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
75628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
76900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
88292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1067 ms |
37128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
