#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn=1000000+10;
bool check(long long a){
for(long long i=2;i*i<=a;i++){
if(a%i==0){
return 0;
}
}
return 1;
}
long long getav(long long a){
while(check(a)==0){
a++;
}
return a;
}
long long mod=getav(rng()%100000000+993847562),base=getav(rng()%200+1000),mp[maxn];
void aval(){
mp[0]=1;
for(long long i=1;i<maxn;i++){
mp[i]=1ll*mp[i-1]*base%mod;
}
}
void solve(){
string s;
cin>>s;
long long n=s.size();
long long mid=n/2;
string first,second;
for(long long i=0;i<mid;i++){
first.push_back(s[i]);
}
for(long long i=mid+(n&1);i<n;i++){
second.push_back(s[i]);
}
long long i=0,j=(long long)second.size()-1;
long long res=0;
long long hash1=0,hash2=0;
long long last=0;
for(long long asd=0;asd<(long long)first.size();asd++){
hash1+=mp[i-last]*first[i];
hash2=hash2*base+second[j];
hash1%=mod;
hash2%=mod;
//cout<<asd<<" "<<first[i]<<" "<<second[j]<<" "<<hash1<<" "<<hash2<<endl;
if(hash1==hash2){
res+=2;
hash1=hash2=0;
last=asd+1;
}
i++;
j--;
}
res++;
cout<<res<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("inp.txt","r",stdin);
aval();
long long t;
cin>>t;
for(long long asd=0;asd<t;asd++){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
