#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=300010, LOG=21;
int n, m, k, u, v, x, y, t, a, b;
ll ans;
int Rank[MAXN<<1][LOG], P[MAXN<<1], pw;
int lcp[MAXN], L[MAXN], R[MAXN];
vector<int> seg[MAXN<<2];
string S;
inline bool cmp(int x, int y){
if (Rank[x][pw-1]!=Rank[y][pw-1]) return Rank[x][pw-1]<Rank[y][pw-1];
if (max(x, y)+(1<<(pw-1))>=m) return x>y;
return Rank[x+(1<<(pw-1))][pw-1]<Rank[y+(1<<(pw-1))][pw-1];
}
void BuildSuffixArray(){
for (int i=0; i<m; i++) Rank[i][0]=S[i], P[i]=i;
for (pw=1; pw<LOG; pw++){
sort(P, P+m, cmp);
Rank[P[0]][pw]=0;
for (int i=1; i<m; i++) Rank[P[i]][pw]=Rank[P[i-1]][pw] + cmp(P[i-1], P[i]);
}
}
int GetLcp(int x, int y){
if (x>y) swap(x, y);
int res=0;
for (int i=LOG-1; ~i; i--) if (y<m && Rank[x][i]==Rank[y][i]){
x+=(1<<i);
y+=(1<<i);
res|=(1<<i);
}
return res;
}
void Add(int id, int tl, int tr, int l, int r, int val){
//if (id==1) cerr<<"Add "<<l<<' '<<r<<' '<<val<<endl;
if (r<=tl || tr<=l) return ;
if (l<=tl && tr<=r){
seg[id].pb(val);
return ;
}
int mid=(tl+tr)>>1;
Add(id<<1, tl, mid, l, r, val);
Add(id<<1 | 1, mid, tr, l, r, val);
}
int GetPalindrome(int id, int tl, int tr, int pos, int val){
if (pos<tl || tr<=pos) return 0;
int res=0;
if (seg[id].size() && seg[id][0]<val) res=(*--lower_bound(all(seg[id]), val))-2*pos+1;
if (tr-tl==1) return res;
int mid=(tl+tr)>>1;
return max(res, max(GetPalindrome(id<<1, tl, mid, pos, val), GetPalindrome(id<<1 | 1, mid, tr, pos, val)));
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>S;
n=S.size();
S+="#";
for (int i=n-1; ~i; i--) S+=S[i];
m=S.size();
BuildSuffixArray();
/*
debug(S)
debug(GetLcp(0, 2*n))
for (int i=0; i<m; i++) cerr<<P[i]<<" \n"[i==m-1];
*/
for (int i=0; i<n; i++){
int len=GetLcp(i+1, 2*n-i);
Add(1, 0, n, i+1-len, i+1, 2*i+1);
ans=max(ans, 2ll*len);
}
for (int i=0; i<n; i++){
int len=GetLcp(i, 2*n-i);
Add(1, 0, n, i-len+1, i+1, 2*i);
ans=max(ans, 2*len-1ll);
}
for (int i=0; i<4*MAXN; i++) sort(all(seg[i]));
/*
int ted=0;
for (int i=0; i<m; i++) if (P[i]<n) P[ted++]=P[i];
*/
for (int i=0; i+1<n; i++) lcp[i]=GetLcp(P[i], P[i+1]);
for (int i=0; i+1<n; i++) for (L[i]=i-1; ~L[i] && lcp[L[i]]>=lcp[i]; L[i]=L[L[i]]);
for (int i=n-2; i; i--) for (R[i]=i+1; R[i]<n-1 && lcp[R[i]]>=lcp[i]; R[i]=R[R[i]]);
for (int i=0; i<=n-2; i++){
ll ted=(R[i]-L[i]);
ans=max(ans, GetPalindrome(1, 0, n, P[i], 2*P[i]+lcp[i])*ted);
//debug2(P[i], GetPalindrome(1, 0, n, P[i], 2*P[i]+lcp[i]))
}
cout<<ans<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
28544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
31352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
868 ms |
56452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1101 ms |
80880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
