#include <bits/stdc++.h>
using namespace std;
int t;
string s;
long long h[1000001];
vector<char> res;
long long base = 31,mod = 1000000007;
long long exp0[1000001];
int siz;
long long getHash(int l,int r){
long long re;
if(l == 0) re = h[r];
else re = (h[r] - h[l - 1] + mod) % mod;
re = (re * exp0[1000000 - l])%mod;
return re;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("censor.in","r",stdin);
//freopen("censor.out","w",stdout);
exp0[0] = 1;
for(int i = 1;i <= 1000000;i++) exp0[i] = (exp0[i - 1] * base) % mod;
cin >> t;
while(t--){
int res = 0;
cin >> s;
//cout << s << "\n";
h[0] = (int) s[0] - 'a' + 1;
siz = s.size();
for(int i = 1;i < siz;i++){
h[i] = (h[i - 1] + ((int) s[i] - 'a' + 1)*exp0[i])%mod;
}
int l = 0,r = siz - 1,lastL = 0,lastR = siz - 1;
bool en = false;
while(l <= r){
if(getHash(lastL,l) == getHash(r,lastR)){
//cout << lastL << " " << l << " " << r << " " << lastR << "\n";
if(l == r) res++;
else res += 2;
lastL = l + 1;
lastR = r - 1;
if(lastL > lastR){
en = true;
}
}
l++;
r--;
}
if(!en) res++;
cout << res << "\n";
}
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... |