#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define LOG 20
typedef long long ll;
const ll p1 = 91;
const ll MOD = 1e9+7;
int n;
string s;
struct entry {
int rnk[2];
int idx;
};
entry order[MAXN];
int rmq[MAXN][LOG];
int suffixarray[MAXN];
int lcp[MAXN];
bool cmp(entry a,entry b){return a.rnk[0]==b.rnk[0] ? (a.rnk[1]<b.rnk[1]):(a.rnk[0]<b.rnk[0]); }
int now;
void build_suffixarray()
{
now=1;
for(int i = 0; i < n; i++)rmq[i][0]=s[i]-'a';
for(int l = 1; l < n; now++,l*=2)
{
for(int i = 0; i < n; i++)
{
order[i].rnk[0]=rmq[i][now-1];
order[i].rnk[1]=(i+l<n)?rmq[i+l][now-1]:-1;
order[i].idx=i;
}
sort(order,order+n,cmp);
for(int i = 0; i < n; i++)
{
rmq[order[i].idx][now]=( i > 0 && order[i].rnk[0] == order[i-1].rnk[0] && order[i].rnk[1] == order[i-1].rnk[1] ) ? rmq[order[i-1].idx][now] : i;
}
}
for(int i = 0; i < n; i++)suffixarray[rmq[i][now-1]]=i;
}
int calc_lcp(int a,int b)
{
int ret = 0;
for(int j = now-1; j >= 0; j--)
{
if(rmq[a][j]==rmq[b][j])a+=(1<<j),b+=(1<<j),ret+=(1<<j);
}
return ret;
}
void build_lcparray()
{
for(int i = 0; i < n-1; i++)
{
lcp[i]=calc_lcp(suffixarray[i],suffixarray[i+1]);
}
for(int i = 0; i < n-1; i++)rmq[i][0]=lcp[i];
for(int j = 1; j < LOG; j++)for(int i = 0; i < n; i++)if(i+(1<<j)<n)rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<j)][j-1]);
}
ll pw[MAXN];
ll invpw[MAXN];
ll sum[MAXN];
ll revsum[MAXN];
ll maxodd[MAXN];
ll maxeven[MAXN];
ll mulmod(ll x,ll y){x*=y;x%=MOD;return x;}
ll addmod(ll x,ll y){x+=y;x+=2*MOD;x%=MOD;return x;}
ll fastpow(ll x,int s)
{
if(s==0)return 1LL;
if(s%2==0)
{
ll y = fastpow(x,s/2);
return mulmod(y,y);
}
return mulmod(x,fastpow(x,s-1));
}
ll geth(ll x,int s)
{
return mulmod(x,pw[s]);
}
ll get(int l,int r)
{
ll ret = sum[r];
if(l>0)ret=addmod(ret,-sum[l-1]);
ret=mulmod(ret,invpw[l]);
return ret;
}
ll getrev(int l,int r)
{
ll ret = revsum[r];
if(l>0)ret=addmod(ret,-revsum[l-1]);
ret=mulmod(ret,invpw[n-r-1]);
return ret;
}
bool palindrome(int l,int r){return get(l,r)==getrev(l,r);}
void calc_hash()
{
pw[0]=1LL;
for(int i = 1; i < MAXN; i++)pw[i]=mulmod(pw[i-1],p1);
invpw[0]=1LL;
ll invp = fastpow(p1,MOD-2);
for(int i = 1; i < MAXN; i++)invpw[i]=mulmod(invpw[i-1],invp);
for(int i = 0; i < n; i++){sum[i]=geth(s[i],i);if(i>0)sum[i]=addmod(sum[i],sum[i-1]);}
for(int i = 0; i < n; i++){revsum[i]=geth(s[i],n-i-1);if(i>0)revsum[i]=addmod(revsum[i],revsum[i-1]);}
for(int i = 0; i < n; i++)
{
ll r=1;
int lo=1,hi=n,mid=lo+hi>>1;
while(lo<=hi)
{
if(i-mid+1<0 || i+mid-1 >= n)hi=mid-1;
else if(palindrome(i-mid+1,i+mid-1))r=mid,lo=mid+1;
else hi=mid-1;
mid=lo+hi>>1;
}
maxodd[i-r+1]=max(maxodd[i-r+1],2*r-1);
}
for(int i = 0; i < n; i++)
{
ll r=0;
int lo=1,hi=n,mid=lo+hi>>1;
while(lo<=hi)
{
if(i-mid+1 < 0 || i+mid-1+1 >= n)hi=mid-1;
else if(palindrome(i-mid+1,i+mid-1+1))r=mid,lo=mid+1;
else hi=mid-1;
mid=lo+hi>>1;
}
if(r==0)continue;
maxeven[i-r+1]=max(maxeven[i-r+1],2*r);
}
}
int getlcp(int x,int y)
{
y--;
if(x>y)return 0;
int d = log2(y-x+1);
int ret = 123213231;
ret=min(ret,rmq[x][d]);
ret=min(ret,rmq[y-(1<<d)+1][d]);
return ret;
}
void calc_ans()
{
ll ans = 0LL;
for(int i = 0; i < n; i++)
{
ll r=1;
int lo=2,hi=n,mid=lo+hi>>1;
while(lo<=hi)
{
if(i+mid-1>=n)hi=mid-1;
else if(getlcp(i,i+mid-1)>=maxodd[suffixarray[i]])r=mid,lo=mid+1;
else hi=mid-1;
mid=lo+hi>>1;
}
ll r1=1;
lo=2,hi=n,mid=lo+hi>>1;
while(lo <= hi)
{
if(i-mid+1<0)hi=mid-1;
else if(getlcp(i-mid+1,i)>=maxodd[suffixarray[i]])r1=mid,lo=mid+1;
else hi=mid-1;
mid=lo+hi>>1;
}
ans=max(ans,(r+r1-1)*maxodd[suffixarray[i]]);
}
for(int i = 0; i < n; i++)
{
ll r=1;
int lo=2,hi=n,mid=lo+hi>>1;
while(lo<=hi)
{
if(i+mid-1>=n)hi=mid-1;
else if(getlcp(i,i+mid-1)>=maxeven[suffixarray[i]])r=mid,lo=mid+1;
else hi=mid-1;
mid=lo+hi>>1;
}
ll r1=1;
lo=2,hi=n,mid=lo+hi>>1;
while(lo <= hi)
{
if(i-mid+1<0)hi=mid-1;
else if(getlcp(i-mid+1,i)>=maxeven[suffixarray[i]])r1=mid,lo=mid+1;
else hi=mid-1;
mid=lo+hi>>1;
}
ans=max(ans,(r+r1-1)*maxeven[suffixarray[i]]);
}
cout << ans;
}
void debug()
{
for(int i = 0; i < n; i++)
{
cout << i << " " << maxeven[i] << " " << maxodd[i] << "\n";
}
for(int i = 0; i < n; i++)
{
for(int j = suffixarray[i]; j < s.length(); j++)
{
cout << s[j];
}
cout << "\n";
}
cout << "LCP: ";
for(int i = 0; i < n; i++)
{
cout << lcp[i] << " ";
}
cout << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s;
n = s.length();
build_suffixarray();
build_lcparray();
calc_hash();
//debug();
calc_ans();
return 0;
}
Compilation message
palindrome.cpp: In function 'void calc_hash()':
palindrome.cpp:111:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int lo=1,hi=n,mid=lo+hi>>1;
~~^~~
palindrome.cpp:117:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
palindrome.cpp:124:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int lo=1,hi=n,mid=lo+hi>>1;
~~^~~
palindrome.cpp:130:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
palindrome.cpp: In function 'void calc_ans()':
palindrome.cpp:154:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int lo=2,hi=n,mid=lo+hi>>1;
~~^~~
palindrome.cpp:160:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
palindrome.cpp:163:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
lo=2,hi=n,mid=lo+hi>>1;
~~^~~
palindrome.cpp:169:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
palindrome.cpp:176:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int lo=2,hi=n,mid=lo+hi>>1;
~~^~~
palindrome.cpp:182:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
palindrome.cpp:185:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
lo=2,hi=n,mid=lo+hi>>1;
~~^~~
palindrome.cpp:191:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
palindrome.cpp: In function 'void debug()':
palindrome.cpp:206:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = suffixarray[i]; j < s.length(); j++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
5296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
6412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
328 ms |
17400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
41912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
