#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int b=911;
int ph[N];
int p[N];
void h(string s){
int n=s.size();
ph[0]=s[0];
for(int i=1; i<n; i++){
ph[i]=ph[i-1]*b+s[i];
}
}
int get(int l, int r){
if(l==0){
return ph[r];
}else{
return ph[r]-ph[l-1]*p[r-l+1];
}
}
signed main(){
int t;
cin >> t;
p[0]=1;
for(int i=1; i<N; i++){
p[i]=p[i-1]*b;
}
while(t--){
int ans=0;
string s;
cin >> s;
int n=s.size();
int l=0, r=n-1;
h(s);
while(l<r){
bool g=false;
for(int i=1; l+i-1<r-i+1; i++){
if(get(l, l+i-1)==get(r-i+1, r)){
ans+=2;
l+=i;
r-=i;
g=true;
break;
}
// if(l!=r){
// ans++;
// }
}
if(g==false){
break;
}
}
if(l<=r){
ans++;
}
cout << ans << endl;
}
}
# | 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... |