#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;} inline void mod(int x,int k){ if(!x)return ; 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(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){ 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); 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]; const int INF=1e9; 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; } int tg[2000300]; 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("proud5.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); } g[0].push_back(1); dfs(0); dfs(0,0); gdp[0]=0; int P=0; for(int i=1;i<=n;i++){ P=min(P,tg[i]); gdp[i]=min(gdp[i-1]+1,P+i); fdp[i]=gdp[i]+1; int lst=i+1; int w=0; for(int x:sp[i]){ tg[lst]=min(tg[lst],fdp[i]-i-(i-1)*w); lst=x; w++; } } // cerr<<Sss<<endl; cout<<gdp[n]<<endl; cout.flush(); return 0; }