이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
int n, mhash[600005], thash[600005], rnk[600005], sa[600005], lcp[600005], even[600006], odd[600005], par[600005], w[3000005], ans, mxw;
stack<int> st;
string s;
int f(int a, int b, int c)
{
assert(a<=1e6 and b<=1e6);
return a*(int)1e12+b*(int)1e6+c;
}
bool cmp(int a, int b)
{
return thash[a]<thash[b];
}
void build(int len, int N)
{
int hlf = len>>1;
if(hlf) build(hlf, N);
for(int i=1; i<=N; i++)
{
sa[i] = i;
thash[i] = len==1? (int)s[i]: f(mhash[i], mhash[i+hlf], (len&1? (int)s[i+len-1]: 0));
}
sort(sa+1, sa+N+1, cmp);
for(int i=1; i<=N; i++)
{
mhash[sa[i]] = i==1? 1: mhash[sa[i-1]]+cmp(sa[i-1], sa[i]);
}
}
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[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+'$'+s;
build(n, n); // ban dau la build(n, n)
for(int i=1; i<=n; i++)
{
rnk[sa[i]] = i;
}
int curl = 0;
for(int i=1; i<=n; i++)
{
if(rnk[i]==n)
{
lcp[rnk[i]] = 0;
continue;
}
int j = sa[rnk[i]+1];
while(s[i+curl]==s[j+curl])
{
curl++;
}
lcp[rnk[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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |