#include<iostream>
#include<cstdio>
#define N 1000001
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
string s;
int n,length,top,rt[N+1],tmp[N+1],lg[N+1],dp[N+1],ps[N+1],scnt[N+1],sa[N+1],h[N+1],rk[N+1],cnt[N+1],delta[N+1][21],delta2[N+1][21];
char c[N+1];
bool vis[N+1];
struct reads
{
	int l,r,d;
};
reads dque[N+1];
struct seg
{
	struct node
	{
		int ls,rs,data;
	};
	node tree[30*N+1];
	int length;
	void push_up(int k)
	{
		tree[k].data=tree[tree[k].ls].data+tree[tree[k].rs].data;
		return;
	}
	int add(int k,int L,int R,int x,int d)
	{
		int nw=++length;
		tree[nw]=tree[k];
		if (L==R)
		{
			tree[nw].data+=d;
			return nw;
		}
		int mid=(L+R)>>1;
		if (x<=mid) tree[nw].ls=add(tree[nw].ls,L,mid,x,d);
		else tree[nw].rs=add(tree[nw].rs,mid+1,R,x,d);
		push_up(nw);
		return nw;
	}
	int query(int k,int L,int R,int l,int r)
	{
		if (!k) return 0;
		if (L==l&&R==r) return tree[k].data;
		int mid=(L+R)>>1;
		if (r<=mid) return query(tree[k].ls,L,mid,l,r);
		else if (l>=mid+1) return query(tree[k].rs,mid+1,R,l,r);
		else return query(tree[k].ls,L,mid,l,mid)+query(tree[k].rs,mid+1,R,mid+1,r);
	}
};
seg T;
void build_SA()
{
	for (int i=1;i<=n;++i) ps[i]=++cnt[c[i]-'a'+1];
	for (int i=1;i<=26;++i) scnt[i]=scnt[i-1]+(cnt[i]>0),cnt[i]+=cnt[i-1];
	for (int i=1;i<=n;++i) sa[cnt[c[i]-'a']+ps[i]]=i,rk[i]=scnt[c[i]-'a'+1];
	length=scnt[26];
	for (int i=1;length<n;i<<=1)
	{
		for (int j=1;j<=length;++j) cnt[j]=0;
		for (int j=n-i+1;j<=n;++j) ps[j]=++cnt[rk[j]];
		for (int j=1;j<=n;++j)
			if (sa[j]>=i+1)
				ps[sa[j]-i]=++cnt[rk[sa[j]-i]];
		for (int j=1;j<=length;++j) cnt[j]+=cnt[j-1];
		for (int j=1;j<=n;++j) sa[cnt[rk[j]-1]+ps[j]]=j;
		length=0;
		for (int j=1;j<=n;++j)
		{
			if (j==1||rk[sa[j]]!=rk[sa[j-1]]||(sa[j]+i<=(n<<1)?rk[sa[j]+i]:0)!=(sa[j-1]+i<=(n<<1)?rk[sa[j-1]+i]:0)) ++length;
			tmp[sa[j]]=length;
		}
		for (int j=1;j<=n;++j) rk[j]=tmp[j];
		for (int j=1;j<=length;++j) vis[j]=0;
	}
	for (int i=1;i<=n;++i)
	{
		h[rk[i]]=max(h[rk[i-1]]-1,0);
		if (rk[i]!=1)
		{
			while (i+h[rk[i]]<=n&&c[i+h[rk[i]]]==c[sa[rk[i]-1]+h[rk[i]]]) h[rk[i]]++;
		}
	}
	return;
}
int calc(int l,int r)
{
	int d=r-l+1,sl=rk[l],sr=rk[l];
	for (int i=lg[n];i>=0;--i)
		if (sr+(1<<i)<=n&&delta[sr][i]>=d)
			sr+=(1<<i);
	for (int i=lg[n];i>=0;--i)
		if (sl-(1<<i)>=1&&delta2[sl][i]>=d)
			sl-=(1<<i);
	return T.query(rt[l],1,n,sl,sr)-dp[r+1];
}
int main()
{
	int ps;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	cin>>s,n=s.length();
	for (int i=1;i<=n;++i) c[i]=s[i-1];
	build_SA();
	for (int i=n;i>=1;--i) rt[i]=T.add(rt[i+1],1,n,rk[i],1);
	for (int i=2;i<=n;++i) delta[i-1][0]=delta2[i][0]=h[i];
	for (int i=1;i<=lg[n];++i)
	{
		for (int j=1;j<=n-(1<<i);++j) delta[j][i]=min(delta[j][i-1],delta[j+(1<<(i-1))][i-1]);
		for (int j=(1<<i)+1;j<=n;++j) delta2[j][i]=min(delta2[j][i-1],delta2[j-(1<<(i-1))][i-1]);
	}
	for (int i=n;i>=1;--i)
	{
		if (i!=n)
		{
			if (dque[top].l==i+1) top--;
			else dque[top].r--;
		}
		while (top&&calc(dque[top].l,i)>calc(dque[top].l,dque[top].d)) top--;
		if (top&&calc(dque[top].r,i)>calc(dque[top].r,dque[top].d))
		{
			ps=dque[top].r;
			for (int j=lg[dque[top].r-dque[top].l+1];j>=0;--j)
				if (ps-(1<<j)>=dque[top].l&&calc(ps-(1<<j),i)>calc(ps-(1<<j),dque[top].d))
					ps-=(1<<j);
			dque[top].r=ps-1;
		}
		ps=dque[top].r+1;
		if (ps<=i) dque[++top]=(reads){ps,i,i};
		dp[i]=calc(i,dque[top].d);
	}
	printf("%d\n",dp[1]);
	return 0;
}