#include<bits/stdc++.h>
#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back//khi dùng pair
#define emb emplace_back//k pair
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+3;
int n,ans,base=31;
string s;
long long f[N],c[N];
int kc(int i,int j){
return ((1LL*f[j]-1LL*f[i-1]*c[j-i+1])%mod+mod)%mod;
}
void solve(){
ans=0;
cin >> s;
n=s.size();
s=" "+s;
int r=1,l=n;
for(int i=1;i<=n;++i)f[i]=(f[i-1]*base+s[i]-'a'+1)%mod;
for(int i=1,j=n;i<=j;++i,--j){
if(kc(r,i)==kc(j,l)){
// cout <<r<<" "<<i<<" "<<j<<" "<<l<<'\n';
r=i+1;l=j-1;
ans+=2;
if(i==j)--ans;
}
}
cout << ans;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
c[0]=1;
for(int i=1;i<=N-5;++i)c[i]=(c[i-1]*base)%mod;
int t=1;
cin >> t;
while(t--){
solve();
cout<<'\n';
}
}
Compilation message
palindromic.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
43 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
