#include<iostream> #include<cstring> #include<vector> #include<cstring> #include<ctime> #include<cassert> #include<queue> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; const int N=2000100,sig=2,LG=21,inf=0x3f3f3f3f; int n,lcp[N]; char s[N]; int fail[N]; void get_lcp(){ int mx=1; for(int i=2;i<=n;i++){ if(mx+lcp[mx]-1>=i)lcp[i]=min(mx+lcp[mx]-i,lcp[i-mx+1]); while(i+lcp[i]<=n&&s[i+lcp[i]]==s[1+lcp[i]])lcp[i]++; if(i+lcp[i]>mx+lcp[mx])mx=i; } lcp[1]=n; } void get_fail(){ for(int i=2;i<=n;i++){ fail[i]=fail[i-1]; while(fail[i]&&s[fail[i]+1]!=s[i])fail[i]=fail[fail[i]]; if(s[fail[i]+1]==s[i])fail[i]++; } } int nex[N]; int find(int x){return nex[x]==x?x:nex[x]=find(nex[x]);} vector<int>pos[N]; void init(){ scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n+1;i++)nex[i]=i; get_lcp(); get_fail(); for(int i=1;i<=n;i++)pos[lcp[i]].emplace_back(i); } int f[N]; int main(){ // freopen("proud.in","r",stdin); // freopen("proud.out","w",stdout); init(); memset(f,0x3f,sizeof(f)); f[1]=1; for(int p:pos[0])nex[p]=p+1; for(int i=1;i<n;i++){ f[i+1]=min(f[i+1],f[i]+1); int x=find(i+1); int cnt=1; while(x<=n){ f[x+i-1]=min(f[x+i-1],f[i]+x-(i-1)*cnt); x=find(x+i); cnt++; } for(int p:pos[i])nex[p]=p+1; } cout<<f[n]; // cerr<<timeMS<<endl; return 0; }