This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll mod=1e9+7;
const ll maxn=1e6+500;
const ll inf=1e9+900;
const ll base=373;
ll tav[maxn];
ll h[maxn];
string globs;
void make_hash(string s){
globs=s;
ll n=s.size();
h[0]=s[0];
for(ll i=1;i<n;i++){
h[i]=(h[i-1]*base+s[i])%mod;
}
}
inline ll ok(ll a){
if(a>=mod)return a-mod;
return a;
}
ll find_hash(ll l,ll r){
if(l==0)return h[r];
return ok(h[r]-(h[l-1]*tav[r-l+1])%mod+mod);
}
bool is_equal(ll l,ll r,ll L,ll R){
// cout<<l<<' '<<r<<' '<<L<<' '<<R<<":"<<(find_hash(l,r)==find_hash(L,R))<<endl;
return (find_hash(l,r)==find_hash(L,R));
}
ll dp[maxn];
ll maxT[maxn];
ll minT[maxn];
ll kia[maxn];
ll solve(string s){
ll n=s.size();
make_hash(s);
memset(maxT,0,sizeof maxT);
memset(dp,0,sizeof dp);
memset(minT,0,sizeof minT);
memset(kia,0,sizeof kia);
for(ll l=(n-1)/2;l>=0;l--){
ll r=n-l-1;
if(l==r){
maxT[l]=0;
}
else{
maxT[l]=0;
ll res=min(r-l,maxT[l+1]+2);
while(res>0 && !is_equal(l,l+res-1,r-res+1,r)){
res--;
}
maxT[l]=res;
}
}
for(ll l=(n-1)/2;l>=0;l--){
ll r=n-l-1;
if(l==r){
minT[l]=1;//set kia?
}
if(maxT[l]*2<=r-l+1){
ll last=maxT[l]+l-1;
ll v=kia[last];
if(v!=0){
minT[l]=v-l;
}else{
minT[l]=maxT[l];
if(minT[l]==0){
minT[l]=r-l+1;
}
}
kia[last]=l;
}else{
ll t=maxT[l]*2-(r-l+1);
minT[l]=minT[(n-t)/2];
}
}
for(ll l=(n-1)/2;l>=0;l--){
ll r=n-l-1;
if(l==r){
dp[l]=1;
}
else{
if(minT[l]==r-l+1){
dp[l]=1;
}else{
dp[l]=2+dp[l+minT[l]];
}
}
// cout<<l<<' '<<r<<":"<<minT[l]<<' '<<maxT[l]<<' '<<dp[l]<<endl;
}
return dp[0];
}
int main(){
tav[0]=1;
for(ll i=1;i<maxn;i++){
tav[i]=(tav[i-1]*base)%mod;
}
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll t;
cin>>t;
while(t--){
string s;
cin>>s;
cout<<solve(s)<<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... |