Submission #1264688

#TimeUsernameProblemLanguageResultExecution timeMemory
1264688uzukishinobuPalindromic Partitions (CEOI17_palindromic)C++20
100 / 100
157 ms19536 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a; string s; int h[1000005]; int h1[1000005]; int mu[1000005]; int base=31; int mod=1e9+7; int gethash(int l,int r){ return (h[r]-h[l-1]*mu[r-l+1]%mod +mod)%mod; } void solve(){ cin >> s; a=s.size(); s='#'+s; mu[0]=1; h[0]=0; for (int i=1;i<=a;i++){ h[i]=(h[i-1]*base+ (s[i]-'a'+1))%mod; mu[i]=(mu[i-1]*base)%mod; } int l=1,r=a; int l1=1,r1=a; int ans=0; while (l<r){ if (gethash(l1,l)==gethash(r,r1)){ ans+=2; l1=l+1; r1=r-1; } l++; r--; } ans+=(l1<=r1); cout << ans << "\n"; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--){ solve(); } 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...