#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
#define dbg(x) cout<<#x<<" has a value of: "<<x<<"\n";
#define usize(x) (int)(x.size())
#define plist(x) for(int i=0;i<usize(x);i++)cout<<"eleman "<<i<<" = "<<x[i]<<"\n";
#define foreach(x) for(auto item:x)
#define fill(s,x) for(int i=0;i<x;i++)cin>>s[i];
std::ostream& operator<<(std::ostream& os, pair<int,int> p) {
os << p.first << ", " << p.second;
return os;
}
const lli HASH_MOD=1e9+7;
const lli HASH_BASE=37;
lli extended(lli a,lli b,lli* x, lli* y){
if(a==0){
*x=0;
*y=1;
return b;
}
lli x1,y1;
lli gcdv=extended(b%a,a,&x1,&y1);
*x=y1-(b/a)*x1;
*y=x1;
return gcdv;
}
lli inverse(lli a){
lli x,y;
extended(a,HASH_MOD,&x,&y);
return (x+HASH_MOD)%HASH_MOD;
}
lli fastPow(lli a,lli b){
if(b==0)return 1;
lli snc=fastPow(a,b/2)*fastPow(a,b/2);
snc=(snc+HASH_MOD)%HASH_MOD;
if(b&1)snc*=a;
return (snc+HASH_MOD)%HASH_MOD;
}
/*
4 bonobo deleted racecar racecars
* */
int main(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int n=s.size();
vector<lli> pre(n+1);
for(int i=0;i<n;i++){
pre[i+1]=(pre[i]*HASH_BASE+s[i]-'a'+1+HASH_MOD)%HASH_MOD;
}
lli cvb=0;
lli cst=0,cend=n;
int i=1;
for(;;){
if(cst+i>=cend-i+1)break;
//dbg(i);
//dbg(cst);
lli on=((pre[cst+i]-pre[cst]*fastPow(HASH_BASE,i))+HASH_MOD)%HASH_MOD;
lli son=(((pre[cend]-pre[cend-i]*fastPow(HASH_BASE,i))%HASH_MOD)+HASH_MOD)%HASH_MOD;
if(on==son){
cvb+=2;
cst+=i;
cend-=i;
i=1;
}
else i++;
}
if(cst<cend)cvb++;
cout<<cvb<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
