#include <bits/stdc++.h> using namespace std; // #define int long long string s; int n; vector<int>sp[2000300]; int fdp[2000300],gdp[2000300]; const int INF=1e9; int mt[4000300]; int z[2000300]; int f[2003000]; vector<int>A[2000300]; inline int lb(int x){return x&-x;} 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]; inline int ff(int x){return f[x]==x?x:f[x]=ff(f[x]);} 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("proud4.in","r",stdin); // freopen("proud.out","w",stdout); cin>>s; n=s.size(); s=" "+s; int r=0,l=0; for(int i=2;i<=n;i++){ if(i<=r&&z[i-l+1]<r-i+1)z[i]=z[i-l]; else{ z[i]=max(0,r-i+1); while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])z[i]++; } if(i+z[i]-1>=r)r=i+z[i]-1,l=i; A[z[i]].push_back(i); // cout<<i<<" "<<z[i]<<endl; } // return 0; for(int i=1;i<=n+1;i++) f[i]=i; for(int i=1;i<=n;i++){ for(int x:A[i-1])f[x]=x+1;//,cerr<<"!"<<x<<endl;; int x=1; while(x<=n){ x=ff(x+i); // cerr<<x<<endl; sp[i].push_back(x+i-1); } } 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; }