#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
const int mlog = 19;
const ll mod = 1e9 + 7;
int n;
char s[maxn];
ll pw[maxn], en1[maxn], en2[maxn];
int can1[maxn], can2[maxn];
int lay, ra[maxn][25], sa[maxn];
ll add(ll x, ll y) {
return ((x+y)%mod + mod)%mod;
}
ll mul(ll x, ll y) {
return ((x*y)%mod + mod)%mod;
}
ll enc1(int l, int r) {
return add(en1[r], -mul(en1[l], pw[r-l]));
}
ll enc2(int l, int r) {
return add(en2[l], -mul(en2[r], pw[r-l]));
}
bool cmp(int x, int y) {
if(ra[x][lay]!=ra[y][lay]) return ra[x][lay] < ra[y][lay];
return (x+(1<<lay)<=n ? ra[x+(1<<lay)][lay] : -1) <= (y+(1<<lay)<=n ? ra[y+(1<<lay)][lay] : -1);
}
int lcp(int x, int y) {
if(x==y) return n-x+1;
int ret = 0;
for(int i=mlog;i>=0;i--) {
if(ra[x][i]==ra[y][i]) {
ret += (1<<i);
x += (1<<i); y += (1<<i);
}
}
return ret;
}
int get(int i, int val) {
int x = sa[i];
int l, r, mid, posl = i, posr = i;
l = 1; r = i;
while(l<=r) {
mid = (l+r)/2;
if(lcp(sa[mid],x)>=val) {
posl = mid;
r = mid-1;
}
else l = mid+1;
}
l = i; r = n;
while(l<=r) {
mid = (l+r)/2;
if(lcp(sa[mid],x)>=val) {
posr = mid;
l = mid+1;
}
else r = mid-1;
}
return posr-posl+1;
}
int main() {
scanf(" %s",s+1);
n = strlen(s+1);
//1. longest palindrome
pw[0] = 1;
for(int i=1;i<=n;i++) pw[i] = mul(pw[i-1], 101);
en1[0] = 0;
for(int i=1;i<=n;i++) en1[i] = add(mul(en1[i-1], 101), s[i]);
en2[n+1] = 0;
for(int i=n;i>=1;i--) en2[i] = add(mul(en2[i+1], 101), s[i]);
for(int i=1;i<=n;i++) {
int l,r,mid,len;
l = 0; r = min(i,n-i+1) - 1; len = 0;
while(l<=r) {
mid = (l+r)/2;
if(enc1(i-mid,i+mid)==enc2(i-mid,i+mid)) {
len = mid;
l = mid+1;
}
else r = mid-1;
}
can1[i-len] = max(can1[i-len], len*2 + 1);
l = 0; r = min(i,n-i) - 1; len = -1;
while(l<=r) {
mid = (l+r)/2;
if(enc1(i-mid,1+i+mid)==enc2(i-mid,1+i+mid)) {
len = mid;
l = mid+1;
}
else r = mid-1;
}
can2[i-len] = max(can2[i-len], len*2 + 2);
}
for(int i=1;i<=n;i++) {
can1[i] = max(can1[i], can1[i-1] - 2);
can2[i] = max(can2[i], can2[i-1] - 2);
}
//2. longest match
for(int i=1;i<=n;i++) ra[i][0] = s[i], sa[i] = i;
for(lay=0;lay<=mlog;lay++) {
sort(&sa[1],&sa[n+1],cmp);
for(int i=1,cnt=0;i<=n;i++) {
if(i==1 || !cmp(sa[i],sa[i-1])) cnt++;
ra[sa[i]][lay+1] = cnt;
}
}
long long ans = 0;
for(int i=1;i<=n;i++) {
int x = sa[i];
ans = max(ans, (long long)get(i,can1[x])*can1[x]);
ans = max(ans, (long long)get(i,can2[x])*can2[x]);
// printf("%d : %d * %d\n",x,get(i,can1[x]),can1[x]);
// printf("%d : %d * %d\n",x,get(i,can2[x]),can2[x]);
}
printf("%lld",ans);
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s",s+1);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
284 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
364 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
