#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_with_hash(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_with_hash(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] = 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] = (hsh[i - 1] * base + (int)(s[i] - 'a' + 1)) % mod;
}
for (int i = n - 1; i >= 0; i--)
rev[i] = (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:118: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 |
71 ms |
73208 KB |
Output is correct |
| 2 |
Correct |
77 ms |
73080 KB |
Output is correct |
| 3 |
Incorrect |
67 ms |
73208 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
73180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
73692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
706 ms |
78388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
33716 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
