#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e5+10; const int base1=59,base2=61,mod1=998244353,mod2=1011451423; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } string s; int n,z[maxn],f[maxn],g[maxn]; void Z(){ z[1]=n;int l=0,r=0; up(i,2,n){ if(i<=r)z[i]=min(z[i-l+1],r-i+1); while(i+z[i]<=n&&s[1+z[i]]==s[i+z[i]])z[i]++; if(i+z[i]-1>r)l=i,r=i+z[i]-1; } //printf("z:");up(i,1,n)printf("%d ",z[i]);printf("\n"); } struct ST { int t[maxn][20],Log_2[maxn]; void init(){ up(i,2,n)Log_2[i]=Log_2[i>>1]+1; up(i,1,n)t[i][0]=z[i]; up(i,1,Log_2[n])up(j,1,n-(1<<i)+1)t[j][i]=max(t[j][i-1],t[j+(1<<i-1)][i-1]); }int get(int l,int r,int lim){ if(l>r)return -1; int k=Log_2[r-l+1]; if(t[l][k]<lim&&t[r-(1<<k)+1][k]<lim)return -1; down(i,k,0)if(t[l][i]<lim)l+=(1<<i); return l; } }T; void slv(){ cin>>s;n=s.size();s=" "+s;Z(); f[1]=1,g[1]=2;T.init(); int mx=2; up(i,1,n)g[i]=f[i]=1e9;f[1]=1,g[1]=2; up(i,1,n){ if(i!=1)f[i]=min(f[i],f[i-1]+1),g[i]=min(g[i],f[i]+1),f[i]=min(f[i],g[i]); int pos=i,ct=f[i]+1; while(1){ int p=T.get(pos+1,n,i); //cout<<"p:"<<p<<endl; if(p==-1)break;ct+=p-pos; g[p+i-1]=min(g[p+i-1],ct); pos=p+i-1; } mx=min(mx,g[i]-i); }cout<<f[n]; } int main(){ //freopen("proud.in","r",stdin); //freopen("proud.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }