#include<iostream>
#include<cstdio>
#define N 1000001
#define M 21
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],cs[N+1],cnt[N+1],delta[N+1][21],delta2[N+1][21],dque[N+1],L[M+1][N+1],R[M+1][N+1];
char c[N+1];
bool vis[N+1];
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int d)
{
	for (;x<=n;x+=lowbit(x)) cs[x]+=d;
	return;
}
int query(int x)
{
	int res=0;
	for (;x>=1;x-=lowbit(x)) res+=cs[x];
	return res;
}
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];
	if (r-l+1<=M) sl=L[d][sl],sr=R[d][sr];
	else
	{
		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 query(sr)-query(sl-1)-dp[r+1];
}
int main()
{
	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=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=1;i<=M;++i)
	{
		L[i][1]=1,R[i][n]=n;
		for (int j=2;j<=n;++j) L[i][j]=h[j]>=i?L[i][j-1]:j;
		for (int j=n-1;j>=1;--j) R[i][j]=h[j+1]>=i?R[i][j+1]:j;
	}
	for (int i=n;i>=1;--i)
	{
		add(rk[i],1),dque[++top]=i;
		while (top)
		{
			dp[i]=max(dp[i],calc(i,dque[top]));
			if (dp[i]<=dp[dque[top]+1]) top--;
			else break;
		}
	}
	printf("%d\n",dp[1]);
	return 0;
}