#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=2e6+10; 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"); } int fa[maxn]; int fd(int x){if(x==fa[x])return x;return fa[x]=fd(fa[x]);} vector<int>P[maxn]; void slv(){ cin>>s;n=s.size();s=" "+s;Z(); f[1]=1,g[1]=2; up(i,1,n+1)fa[i]=i; up(i,1,n)P[z[i]].p_b(i); up(i,1,n)if(!z[i])fa[i]=i+1; 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=fd(pos+1); //cout<<"p:"<<p<<endl; if(p==n+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); for(int x:P[i])fa[x]=x+1; }cout<<f[n]; } int main(){ //freopen("proud.in","r",stdin); //freopen("proud.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }