#include<bits/stdc++.h> using namespace std; #define ll long long int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=2000010,inf=1e9; int n,k,nx[MAXN],f[MAXN],g[MAXN]; char c[MAXN]; void Min(int &x,int y){x=min(x,y);} void init(){ nx[1]=n,nx[2]=0; while(2+nx[2]<=n&&c[1+nx[2]]==c[2+nx[2]])nx[2]++; int k=2; for(int i=3;i<=n;i++){ int p=k+nx[k]-1,l=nx[i-k+1]; if(i+l-1<p)nx[i]=l; else{ int tmp=max(0,p-i+1); while(i+tmp<=n&&c[1+tmp]==c[i+tmp])tmp++; nx[i]=tmp; k=i; } } } #define pb push_back int fa[MAXN]; int fid(int x){return fa[x]==x?x:fa[x]=fid(fa[x]);} void mrge(int u,int v){ int x=fid(u),y=fid(v); if(x!=y)fa[x]=y; } vector<int>D[MAXN]; void slv(){ scanf("%s",c+1); n=strlen(c+1); for(int i=1;i<=n+1;i++)fa[i]=i; init(); for(int i=1;i<=n;i++)D[nx[i]].pb(i);//,cout<<nx[i]<<" ";cout<<endl; memset(g,0x3f,sizeof(g)); int tmp=0; for(auto o:D[0])mrge(o,o+1); for(int i=1;i<=n;i++){ tmp=min(tmp,g[i]-i); f[i]=tmp+i; int now=fid(i+1),cnt=now-i-1; while(now<=n){ cnt++; Min(g[now+i-1],f[i]+cnt+1); // cout<<now<<"_"<<now+i-1<<":"<<f[i]+1<<" "<<cnt<<endl; if(now+i>n)break; now+=i-1; cnt+=fid(now+1)-now-1; now=fid(now+1); } // cout<<f[i]<<" "<<g[i]<<endl; for(auto o:D[i])mrge(o,o+1); tmp=min(tmp,g[i]-i); } printf("%lld",f[n]); } signed main(){ slv(); return 0; }