// Remember...
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=2e6+10,mod=1e9+7;
const ll inf=1e18;
int f[maxn];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int q; cin>>q;
while(q--){
string ss; cin>>ss;
string s="";
for(int i=0;i<=sz(ss)-1-i;i++){
if(i==sz(ss)-1-i) s.PB(ss[i]);
else s.PB(ss[i]), s.PB('+'), s.PB(ss[sz(ss)-1-i]), s.PB('+');
}
if(s.back()=='+') s.pop_back();
int n=sz(s);
int L=-1,R=-1;
for(int i=0;i<n;i++){
if(i<R){
L=R=i;
while(L>0 && R<sz(s)-1 && s[L-1]==s[R+1]) L--,R++;
f[i]=R-i;
}
else{
if(i + f[L+R-i] >= R){
f[i]= R-i;
L=i-f[i];
while(L>0 && R<sz(s)-1 && s[L-1]==s[R+1]) L--,R++;
f[i]=R-i;
}
else{
f[i]= f[L+R-i];
}
}
}
int ans=0;
int nw=0;
while(nw<sz(s)){
int pt=nw+2;
while(pt<sz(s) && 2*f[(nw+pt)>>1]<pt-nw) pt+=2;
if(pt<sz(s)){
ans+=2;
nw=pt+2;
}
else{
ans++;
break;
}
}
cout<<ans<<"\n";
}
return 0;
}
// Deathly mistakes:
// * Read the problem carefully.
// * Check maxn.
// * Overflows.
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
| # |
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 |
- |
