#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define iii pair<ii, int>
#define mp make_pair
#define eb emplace_back
#define vi vector<int>
#define vii vector<ii>
#define viii vector<iii>
#define fi first
#define se second
#define xx fi.fi
#define yy fi.se
#define zz se
const int max_rank = 300005;
int n, even[max_rank], odd[max_rank], par[max_rank], w[max_rank], ans, mxw, cnt[max_rank];
int half_rank[max_rank], full_rank[max_rank], half_sa[max_rank], full_sa[max_rank], sort_by_sec[max_rank], lcp[max_rank];
string s;
int root(int x)
{
return par[x]<0? x: par[x] = root(par[x]);
}
void join(int x, int y)
{
x = root(x), y = root(y);
if(x==y) return;
if(par[x]>par[y]) swap(x, y);
par[x]+=par[y];
w[x]+=w[y];
par[y] = x;
w[y] = 0;
mxw = max(mxw, w[x]);
}
void add(int x)
{
x = root(x);
w[x]++;
mxw = max(mxw, w[x]);
}
void dsu(int arr[], bool bodd)
{
for(int i=1; i<=n; i++)
{
par[i] = -1;
w[i] = 0;
}
mxw = 0;
priority_queue<ii> edge, el;
for(int i=1; i<=n-1; i++) edge.push({lcp[i], i});
for(int i=1; i<=n; i++) el.push({arr[full_sa[i]], i});
for(int len = n; len>=1; len--)
{
while(!el.empty() and el.top().fi>=len)
{
add(el.top().se);
el.pop();
}
while(!edge.empty() and edge.top().fi>=len)
{
join(edge.top().se, edge.top().se+1); // dit me nham thanh .fi moi cay chu
edge.pop();
}
ans = max(ans, mxw*(2*len-bodd));
}
}
signed main()
{
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>s; n = s.length();
s = '$'+s+'$'; n++;
for(int len = 1; len<=(n<<1); len<<=1) // half_sa: last suffix array, half_rank: last rank, full_sa: now suffix array, full_rank: now rank
{
for(int i=1; i<max_rank; i++) cnt[i] = 0;
if(len==1)
{
for(int i=1; i<=n; i++) cnt[s[i]]++;
for(int i=1; i<max_rank; i++) cnt[i]+=cnt[i-1];
for(int i=1; i<=n; i++) full_sa[cnt[s[i]]--] = i;
for(int i=1; i<=n; i++) full_rank[full_sa[i]] = full_rank[full_sa[i-1]]+(s[full_sa[i]]>s[full_sa[i-1]]);
}
else
{
int hlf = len>>1;
for(int i=1; i<=n; i++) half_rank[i] = full_rank[i], half_sa[i] = full_sa[i];
for(int i=1; i<=n; i++) sort_by_sec[i] = half_sa[i]-hlf<1? half_sa[i]-hlf+n: half_sa[i]-hlf;
for(int i=1; i<=n; i++) cnt[half_rank[sort_by_sec[i]]]++;
for(int i=1; i<max_rank; i++) cnt[i]+=cnt[i-1];
for(int i=n; i>=1; i--) full_sa[cnt[half_rank[sort_by_sec[i]]]--] = sort_by_sec[i];
for(int i=1; i<=n; i++)
{
if(i==1) full_rank[full_sa[i]] = 1;
else if(half_rank[full_sa[i]]==half_rank[full_sa[i-1]] and half_rank[(full_sa[i]+hlf-1)%n+1]==half_rank[(full_sa[i-1]+hlf-1)%n+1]) full_rank[full_sa[i]] = full_rank[full_sa[i-1]];
else full_rank[full_sa[i]] = full_rank[full_sa[i-1]]+1;
}
}
}
int curl = 0;
for(int i=1; i<=n; i++)
{
if(full_rank[i]==n)
{
lcp[full_rank[i]] = 0;
continue;
}
int j = full_sa[full_rank[i]+1];
while(s[i+curl]==s[j+curl])
{
curl++;
}
lcp[full_rank[i]] = curl;
if(curl) curl--;
}
int l = 0, r = 0;
for(int i=1; i<=n; i++)
{
if(l<=i and i<=r)
{
odd[i] = min(odd[l+r-i], r-i+1);
}
while(i-odd[i]>=1 and i+odd[i]<=n and s[i-odd[i]]==s[i+odd[i]])
{
odd[i]++;
}
if(odd[i] and r<i+odd[i]-1)
{
r = i+odd[i]-1;
l = i-odd[i]+1;
}
}
l = 0, r = 0;
for(int i=2; i<=n; i++)
{
if(l<=i-1 and i<=r)
{
even[i] = min(even[l+r-i+1], r-i+1); // luc dau quen min o cho nay, toang vai. Nho lan sau phai co!.
}
while(i-1-even[i]>=1 and i+even[i]<=n and s[i-1-even[i]] == s[i+even[i]]) even[i]++;
if(even[i] and r<i+even[i]-1)
{
r = i+even[i]-1;
l = i-even[i];
}
}
dsu(odd, 1);
dsu(even, 0);
cout<<ans;
}
Compilation message
sequence.cpp: In function 'int main()':
sequence.cpp:87:36: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | for(int i=1; i<=n; i++) cnt[s[i]]++;
| ^
sequence.cpp:89:44: warning: array subscript has type 'char' [-Wchar-subscripts]
89 | for(int i=1; i<=n; i++) full_sa[cnt[s[i]]--] = i;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2688 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2688 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2816 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2816 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2816 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2816 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
