This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define be begin()
#define en end()
#define ff first
#define ss second
#define si size()
const ll mod=(1e9)+9;
void solve(){
string s;
cin>>s;
ll n=s.si;
ll l=0, h=n-1;
ll s1=0, s2=0;
ll sum=0;
map<char, ll> mp;
rep(i, 0, 26){
mp[97+i]=i;
}
vector<ll> pw(n+10, 1);
rep(i, 1, n+10){
pw[i]=(pw[i-1]*26)%mod;
}
ll x=0;
while(l<h){
s1=(s1*26)%mod;
s1=(s1+s[l])%mod;
s2=(s2+(pw[x]*s[h])%mod)%mod;
if(s1==s2){
x=-1;
sum+=2;
s1=0, s2=0;
}
x++;
l++, h--;
}
if(s1>0 || s2>0) sum++;
else if(l==h) sum++;
cout<<sum<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |