제출 #670163

#제출 시각아이디문제언어결과실행 시간메모리
670163MohammadAghil회문 (APIO14_palindrome)C++17
0 / 100
158 ms34752 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} void IOS(){ cin.tie(0) -> sync_with_stdio(0); #ifndef ONLINE_JUDGE #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #else #define er(args ...) 0 #endif } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 6e5 + 5, p = 9973, lg = 22, inf = ll(1e9) + 5; // ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;} struct hhh{ vector<int> pw, hsh; ll p, mod; hhh(string s, ll p, ll mod): p(p), mod(mod){ int n = sz(s); hsh.resize(n), pw.resize(n + 1); hsh[0] = s[0]; rep(i,1,n){ hsh[i] = (hsh[i-1]*p + s[i])%mod; } pw[0] = 1; rep(i,1,n+1){ pw[i] = pw[i-1]*p%mod; } } int get(int l, int r){ return (hsh[r] - (l? hsh[l-1]*pw[r-l+1]%mod :0) + mod)%mod; } }; int vl[maxn][2], adj[maxn][26], ptr = 1, hsh[maxn]; map<int, int> id; map<int, bool> is; ll ans; string tmp; void dfs(int r, int h = 0){ // er(r, tmp); rep(i,0,26) if(adj[r][i]){ // tmp.pb(char('a' + i)); dfs(adj[r][i], h+1); // tmp.pop_back(); vl[r][0] += vl[adj[r][i]][0]; vl[r][1] += vl[adj[r][i]][1]; } ans = max({ ans, 2ll*vl[r][0]*h - vl[r][0], 2ll*vl[r][1]*h }); } int main(){ IOS(); string s; cin >> s; int n = sz(s); hhh hs(s, p, mod); reverse(all(s)); hhh hrs(s, p, mod); reverse(all(s)); auto get = [&](int l, int r){ return hs.get(l, r) == hrs.get(n-1-r, n-1-l); }; int tmp = 0, mx = -1; rep(i,0,n){ int lx = 0, rx = min(i+1, mx-i+2); while(lx + 1 < rx){ int mid = (lx + rx)>>1; if(get(i-mid+1, i+mid-1)) lx = mid; else rx = mid; } int cr = lx == 0? 0: id[hs.get(i, i + lx-1)]; if(lx == mx-i+1){ rep(l,rx,min(i+1,n-i)+1){ if(s[i-l+1] == s[i+l-1]){ tmp++; int c = s[i+l-1]-'a'; if(!adj[cr][c]){ hsh[ptr] = (p*hsh[cr] + s[i+l-1])%mod; id[hsh[ptr]] = ptr; adj[cr][c] = ptr++; } cr = adj[cr][c]; mx = i+l-1; } else break; } } vl[cr][0]++; // er(i, mx); // rep(l,rx,min(i+1,n-i)+1){ // if(s[i-l+1] == s[i+l-1]){ // tmp++; // int c = s[i+l-1]-'a'; // if(!adj[cr][c]){ // hsh[ptr] = (p*hsh[cr] + s[i+l-1])%mod; // id[hsh[ptr]] = ptr; // adj[cr][c] = ptr++; // } // cr = adj[cr][c]; // } else break; // } // // er(i, cr); // vl[cr][0]++; } // assert(tmp < 3*n); rep(i,1,n){ if(s[i] - s[i-1]) continue; int lx = 0, rx = min(i, n-i); while(lx + 1 < rx){ int mid = (lx + rx)>>1; if(id.count(hs.get(i, i + mid-1)) && get(i-mid, i+mid-1)) lx = mid; else rx = mid; } int cr = lx == 0? 0: id[hs.get(i, i + lx-1)]; rep(l,rx,min(i,n-i)+1){ if(s[i+l-1] == s[i-l]){ int c = s[i+l-1]-'a'; if(!adj[cr][c]){ hsh[ptr] = (p*hsh[cr] + s[i+l-1])%mod; id[hsh[ptr]] = ptr; adj[cr][c] = ptr++; } cr = adj[cr][c]; } else break; } // er(i, cr); vl[cr][1]++; } dfs(0); cout << ans << '\n'; }
#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...