제출 #537104

#제출 시각아이디문제언어결과실행 시간메모리
537104pooyashams회문 (APIO14_palindrome)C++14
73 / 100
1006 ms99916 KiB
#pragma GCC diagnostic ignored "-Wmisleading-indentation" #pragma GCC optimize("Ofast") #include <algorithm> #include <iostream> #include <numeric> #include <cstring> #include <iomanip> #include <vector> #include <bitset> #include <stack> #include <queue> #include <cmath> #include <set> #include <map> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef vector<int> vi; const int maxn = 3e5+10; const int lgmx = 20; #define rep(i,l,r) for (int i = l; i < r; i++) #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define getat(a,x,y) a[((x)*lgmx)+(y)] struct RMQ { vi vals; int n; RMQ(){} RMQ(vi arr) { n = arr.size(); vals = vi(lgmx*n, 0); for(int i = 0; i < n; i++) getat(vals, i, 0) = arr[i]; for(int k = 1; k < lgmx; k++) { int x = (1<<(k-1)); for(int i = 0; i < n; i++) { if(i+x < n) getat(vals, i, k) = min(getat(vals, i, k-1), getat(vals, i+x, k-1)); else getat(vals, i, k) = getat(vals, i, k-1); } } } int get(int i, int j) { if(i == j) return vals[i*lgmx+0]; int k = __lg(j-i); return min( getat(vals, i, k), getat(vals, j-(1<<k), k) ); } }; struct SuffixArray { int n; vi sa; vi lcp; vi rev; RMQ rlcp; SuffixArray(){}; SuffixArray(string& s, int lim=256) { n = sz(s) + 1; int k = 0, a, b; vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n); rev = vi(n); sa = lcp = y, iota(all(sa), 0); for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) { p = j, iota(all(y), n - j); rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j; fill(all(ws), 0); rep(i,0,n) ws[x[i]]++; rep(i,1,lim) ws[i] += ws[i - 1]; for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i]; swap(x, y), p = 1, x[sa[0]] = 0; rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] = (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++; } rep(i,1,n) rank[sa[i]] = i; rep(i,0,n) rev[sa[i]] = i; for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k) for (k && k--, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; k++); rlcp = RMQ(lcp); } inline int getlcp(int i, int j) { if(i == j) return n-1-i; //if(i == 59) cerr << i << " " << j << endl; i = rev[i]; j = rev[j]; if(i > j) swap(i, j); return rlcp.get(i+1, j+1); } } sfx; int L[maxn]; int R[maxn]; int mr[maxn]; // practically lcp(sfxa[rev[i]], sfxa[rev[i]-1]) + i int mc[maxn]; // int mjm[lgmx][maxn]; // j-mpl[j] (min) ll ans = 0; inline int getmn(int l, int r) // [l, r) { int k = __lg(r-l); return min(mjm[k][l], mjm[k][r-(1<<k)]); } inline int mxpl(int l, int r) // [l, r) { if(r == l) return 0; if(r-l == 1) return 0; // even int i = l; while(r-l > 1) { int k = __lg(r-l-1); int m = r - (1<<k); if(mjm[k][m] > i) r = m; else l = m; } return l-i; } inline void pmjm(int n) { for(int k = 1; k < lgmx; k++) { int x = (1 << (k-1)); for(int i = 0; i < n; i++) { if(i+x < n) mjm[k][i] = min(mjm[k-1][i], mjm[k-1][i+x]); else mjm[k][i] = mjm[k-1][i]; } } } inline void calce(int n) { mjm[0][0] = 0; for(int i = 1; i < n; i++) { //cerr << "alive " << i << endl; mjm[0][i] = i-sfx.getlcp(i, n+n+1-i); } pmjm(n); for(int i = 0; i < n-1; i++) ans = max(ans, 2ll*mxpl(i, (i+n)/2+1)); for(int i = 0; i < n; i++) { if(mr[i] == -1 or mr[i] == i or mr[i] == i+1) continue; int x = mxpl(i, (i+mr[i])/2+1); ans = max(ans, 2ll*mc[i]*x); } } inline void calco(int n) { mjm[0][0] = 0; mjm[0][n-1] = n-1; for(int i = 1; i < n-1; i++) { mjm[0][i] = i-sfx.getlcp(i+1, n+n+1-i); } pmjm(n); for(int i = 0; i < n-1; i++) ans = max(ans, 2ll*mxpl(i, (i+n+1)/2)+1 ); for(int i = 0; i < n; i++) { if(mr[i] == -1 or mr[i] == i) continue; int x = mxpl(i, (i+mr[i]+1)/2); ans = max(ans, 2ll*mc[i]*x+mc[i]); } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; const int n = s.size(); if(n == 1) { cout << 1 << endl; return 0; } sfx = SuffixArray(s); L[1] = 0; R[n] = n+1; for(int i = 2; i <= n; i++) for(L[i] = i-1; L[i] > 0 and sfx.lcp[L[i]] >= sfx.lcp[i]; L[i] = L[L[i]]); for(int i = n-1; i >= 1; i--) for(R[i] = i+1; R[i] <= n and sfx.lcp[R[i]] >= sfx.lcp[i]; R[i] = R[R[i]]); //for(int i = 0; i < ss; i++) cerr << sfxa[i] << " "; cerr << endl; //for(int i = 0; i <= n; i++) cerr << sfx.lcp[i] << " "; cerr << endl; //for(int i = 0; i <= n; i++) cerr << L[i] << " "; cerr << endl; //for(int i = 0; i <= n; i++) cerr << R[i] << " "; cerr << endl; mr[sfx.sa[0]] = -1; mc[sfx.sa[0]] = -1; for(int i = 1; i <= n; i++) { int l = sfx.sa[i]; mr[l] = l+sfx.lcp[i]; mc[l] = R[i]-L[i]; //cerr << l << ": " << mc[l] << " " << mr[l] << endl; } // string t = s; reverse(t.begin(), t.end()); t = s+"#"+t; sfx = SuffixArray(t); calce(n); calco(n); cout << ans << endl; return 0; }
#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...