#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[200300]; int t[8000500]; inline void dfs(int u){ siz[u]=1; for(int v:g[u]){ dfs(v); if(siz[v]>siz[hs[u]])hs[u]=v; siz[u]+=siz[v]; } } inline int lb(int x){return x&-x;} 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){ 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){ 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){ now=gsuf(now+u-1); sp[u].push_back(now); } } 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)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("proud.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); // cerr<<f[i]<<" "<<i<<endl; } // return 0; dfs(0); dfs(0,0); // return 0; bd(1,1,n); gdp[0]=0; for(int i=1;i<=n;i++){ gdp[i]=min(gdp[i-1]+1,gt(1,1,n,i)+i); fdp[i]=gdp[i]+1; int lst=1; int w=0; for(int x:sp[i]){ // cout<<i<<" "<<x<<endl; mod(1,1,n,lst,x-1,fdp[i]-i-(i-1)*w); lst=x; w++; } } cout<<gdp[n]<<endl; cout.flush(); return 0; }