제출 #312183

#제출 시각아이디문제언어결과실행 시간메모리
312183hohohaha회문 (APIO14_palindrome)C++14
73 / 100
1072 ms40212 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...