#include <bits/stdc++.h> using namespace std; // #define int long long string s; int n; int f[2000030]; vector<int>g[2000300]; vector<int>sp[2000300]; int siz[2000300],hs[2003000]; int t[8000500]; inline void dfs(int u){ siz[u]=1; for(int v:g[u]){ dfs(v); if(!hs[u]||siz[v]>siz[hs[u]])hs[u]=v; siz[u]+=siz[v]; } } int Sss=0; inline int lb(int x){return x&-x;} // int ct=0; inline void mod(int x,int k){ if(!x)return ; // cerr<<x<<" "<<k<<endl; while(x<=8e6)t[x]+=k,x+=lb(x); } inline int gt(int x){ x=min(x,n); int res=0; while(x)res+=t[x],x-=lb(x); return res; } inline int gsuf(int x){ int w=gt(x); int now=0; int s=0; int L=21; while(L>=0){ if(s+t[now+(1<<L)]<=w)s+=t[now+(1<<L)],now+=1<<L; L--; } // if(x==10){ // cerr<<now<<" "<<w<<" "<<s<<" "<<gt(now)<<" "<<gt(now+1)<<endl; // } if(gt(now+1)==w)return n+1; return now+1; } inline void OP(int u,int k){ // Sss++; // if(Sss>=5e7){ // cerr<<"cnm sb"<<endl; // exit(0); // } mod(u,k); for(int v:g[u])OP(v,k); } inline void dfs(int u,bool kp){ // cerr<<u<<" "<<kp<<endl; for(int v:g[u])if(v!=hs[u])dfs(v,0); if(hs[u])dfs(hs[u],1); for(int v:g[u])if(v!=hs[u])OP(v,1); // cerr<<u<<" "<<kp<<endl; mod(u,1); if(u){ int now=u; while(now<=n){ // Sss++; // if(Sss>=1e6){ // cerr<<"????"; // exit(0); // } // cerr<<now<<" "<<u<<endl; now=gsuf(now+u-1); sp[u].push_back(now); } } // cerr<<u<<endl; if(!kp)OP(u,-1); } int fdp[2000300],gdp[2000300]; int w[2000300<<2]; #define lc(x) (x<<1) #define rc(x) (x<<1|1) const int INF=1e9; inline void bd(int x,int l,int r){ w[x]=INF; if(l==r)return ; int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); } inline void chkmn(int &x,int y){x=min(x,y);} inline void mod(int x,int l,int r,int L,int R,int k){ if(L<=l&&r<=R){ chkmn(w[x],k); return ; } int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,k); if(R>mid)mod(rc(x),mid+1,r,L,R,k); } inline int gt(int x,int l,int r,int c){ if(l==r)return w[x]; int mid=l+r>>1; if(c<=mid)return min(w[x],gt(lc(x),l,mid,c)); else return min(w[x],gt(rc(x),mid+1,r,c)); } int mt[4000300]; inline void chkmns(int x,int k){ while(x<=n)mt[x]=min(mt[x],k),x+=lb(x); } inline int gmn(int x){ int res=0; while(x)res=min(res,mt[x]),x-=lb(x); return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("proud6.in","w",stdout); // for(int i=1;i<=2e6;i++) // cout<<"b"; // cout.flush(); // return 0; // freopen("proud6.in","r",stdin); // freopen("proud.out","w",stdout); cin>>s; n=s.size(); s=" "+s; int mat=0; for(int i=2;i<=n;i++){ while(mat&&s[mat+1]!=s[i])mat=f[mat]; if(s[mat+1]==s[i])mat++; f[i]=mat; g[f[i]].push_back(i); // cout<<f[i]<<" "; // cout<<f[i]<<" "<<i<<endl; } g[0].push_back(1); // return 0; dfs(0); // for(int i=1;i<=n;i++) // cout<<hs[i]<<"x"<<siz[hs[i]]<<endl; // cout<<endl; dfs(0,0); // return 0; gdp[0]=0; for(int i=1;i<=n;i++){ gdp[i]=min(gdp[i-1]+1,gmn(i)+i); fdp[i]=gdp[i]+1; int lst=i; int w=0; // Sss+=sp[i].size(); for(int x:sp[i]){ chkmns(lst,fdp[i]-i-(i-1)*w); // mod(1,1,n,lst,x-1,fdp[i]-i-(i-1)*w); lst=x; w++; } } // cerr<<Sss<<endl; cout<<gdp[n]<<endl; cout.flush(); return 0; }