#include <bits/stdc++.h>
using namespace std;
int fa[30][500005],fail[500005],n;
char s[500005];
char t[500005];
bool check(int L){
	char c=t[L+1];
	t[L+1]='?';
	int las=L;int now=0;
	for(int i=2;i<=n;++i){
		while(now&&t[now+1]!=s[i])now=fail[now];
		if(t[now+1]==s[i])++now;
		if(now==L){
			//printf("%d %d\n",L,i);
			if(i-las>L){
				t[L+1]=c;
				return false;
			}
			las=i;
		}
	}
	t[L+1]=c;
	return true;
}
int main(){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	if(n==1){
		printf("1\n");
		return 0;
	}
	if(n==2){
		if(s[1]==s[2])printf("1");
		else printf("2");
		return 0;
	}
	for(int i=1;i<=n;++i)t[i]=s[i]; 
	fail[0]=-1;int now;
	for(int i=1;i<=n;++i){
		now=i-1;
		while(now&&s[fail[now]+1]!=s[i])now=fail[now];
		fail[i]=fail[now]+1;
		fa[0][i]=fail[i];
	}
	if(fail[n]==0){
		printf("%d",n);
		return 0;
	}
	for(int i=1;i<=25;++i){
		for(int j=1;j<=n;++j){
			fa[i][j]=fa[i-1][fa[i-1][j]];
		}
	}
	int re=25;now=n;
	while(!fa[re][n])--re;
	while(re>=0){
		if(fa[re][now]&&check(fa[re][now]))now=fa[re][now];
		--re;
	}
	printf("%d",now);
	return 0;
}

思路是，求出fail树，然后用类似倍增的方法贪心最短的合法公共前后缀，本地也拍过了，但是不知道为什么WA一个点。看了下题解思路和我都不一样