제출 #745066

#제출 시각아이디문제언어결과실행 시간메모리
745066zeta7532회문 (APIO14_palindrome)C++17
0 / 100
188 ms860 KiB
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = int; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) int main() { faster; string s; cin >> s; ll N=s.size(); if(N>10000) return 0; vector<ll> A(N+1),B(N+1); A[0]=0; B[N]=0; ll k=1; rep(i,N) A[i+1]=(A[i]+(s[i]-'a'+1)*k)%mod,k=k*100%mod; k=1; for(ll i=N-1;i>=0;i--) B[i]=(B[i+1]+(s[i]-'a'+1)*k)%mod,k=k*100%mod; vector<ll> inv(N); inv[0]=1; rep(i,N-1) inv[i+1]=inv[i]*828542813%mod; unordered_map<ll,ll> M; ll ans=0; for(ll i=0;i<N;i++){ for(ll j=i;j<N;j++){ ll x=(A[j+1]-A[i]+mod)*(inv[i])%mod; ll y=(B[i]-B[j+1]+mod)*(inv[N-j-1])%mod; if(x==y){ M[x]+=j-i+1; ans=max(ans,M[x]); } } } 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...