#include<iostream> #include<cstring> #include<vector> #include<cstring> #include<ctime> #include<queue> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; const int N=2000100,sig=2,LG=21,inf=0x3f3f3f3f; namespace ds{//check min; get_val //标记永久化 int rt,ver,ls[N<<1],rs[N<<1],L[N<<1],R[N<<1],laz[N<<1]; inline int New(int L_,int R_,int ls_,int rs_){ L[++ver]=L_,R[ver]=R_,ls[ver]=ls_,rs[ver]=rs_,laz[ver]=inf; return ver; } int build(int l,int r){ if(l==r)return New(l,r,0,0); int mid=(l+r)>>1; return New(l,r,build(l,mid),build(mid+1,r)); } void chkmin(int l,int r,int k,int nd=rt){ if(l<=L[nd]&&R[nd]<=r){laz[nd]=min(laz[nd],k);return;} if(l<=R[ls[nd]])chkmin(l,r,k,ls[nd]); if(r>=L[rs[nd]])chkmin(l,r,k,rs[nd]); } int get_val(int pos,int nd=rt){ if(L[nd]==R[nd])return laz[nd]; if(pos<=R[ls[nd]])return min(laz[nd],get_val(pos,ls[nd])); else return min(laz[nd],get_val(pos,rs[nd])); } } int n,lcp[N],lg[N],mx[LG][N]; char s[N]; int fail[N],son[N],bro[N],dfn[N],siz[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]++; } } void dfs(int nd,int&dfn_){ siz[nd]=1; dfn[nd]=dfn_++; for(int i=son[nd];i;i=bro[i])dfs(i,dfn_),siz[nd]+=siz[i]; } void init(){ scanf("%s",s+1); n=strlen(s+1); for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; get_lcp(); for(int i=1;i<=n;i++)mx[0][i]=lcp[i]; for(int i=1;i<=lg[n];i++){ for(int j=1;j+(1<<i)-1<=n;j++){ mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]); } } get_fail(); for(int i=1;i<=n;i++)bro[i]=son[fail[i]],son[fail[i]]=i; dfs(0,*(new int(0))); ds::rt=ds::build(1,n); } inline int get_max(int l,int r){ int dL=lg[r-l+1]; return max(mx[dL][l],mx[dL][r-(1<<dL)+1]); } inline int lower(int l,int r,int x){ if(l>r)return 0; while(l<r){ int mid=(l+r)>>1; if(get_max(l,mid)>=x)r=mid; else l=mid+1; } if(lcp[l]>=x)return l; else return 0; } struct node{int pos,id;}; inline bool operator>(const node&A,const node&B){return A.pos>B.pos;} priority_queue<node,vector<node>,greater<>>q; // vector<int>occ[N]; int f[N]; int cnt[N]; int main(){ // freopen("proud.in","r",stdin); // freopen("proud.out","w",stdout); init(); // for(int i=1;i<n;i++){ // int x=lower(i+1,n,i); // while(x){ // occ[x+i-1].emplace_back(i); // x=lower(x+i,n,i); // } // } for(int i=1;i<=n;i++){ while(!q.empty()&&q.top().pos==i){ int x=q.top().id; q.pop(); ds::chkmin(dfn[x],dfn[x]+siz[x]-1,f[x]-(x-1)*(++cnt[x])); int nx=lower(i+1,n,x); if(nx)q.push((node){nx+x-1,x}); } // for(int x:occ[i])ds::chkmin(dfn[x],dfn[x]+siz[x]-1,f[x]-(x-1)*(++cnt[x])); f[i]=min(f[i-1]+1,ds::get_val(dfn[i])+i); ds::chkmin(dfn[i],dfn[i]+siz[i]-1,f[i]-(i-1)*(++cnt[i])); int nx=lower(i+1,n,i); if(nx)q.push((node){nx+i-1,i}); } cout<<f[n]; // cerr<<timeMS<<endl; return 0; }