【学习笔记】后缀数组

发表于

后缀数组吼啊
（据说sam更好啊等我肝完后缀数组就去看sam

之前学了一遍倍增又忘了
论文中的变量名简直不让人学会
把下标和含义说清楚的博客
所以我的板子一定要给数组含义
rk_[i]=j表示后缀i的排名
rk1[]中会有相同的排名，但是sa[]的下标（也就是排名）是没有相同的
sa[i]=j表示排名i的后缀
对后缀i，lcp[i]>=lcp[i-1]+1

多次求sa的话记得先把cnt清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008;
int n;
char s[N]; 
int sa[N],rk[N],a[N],b[N],cnt[N];
inline void get_sa()
{
	int m=128;
	int *rk_1=a,*sa_2=b,*tmp;
    //for i = 1 to m cnt[i]=0
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}	
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
int lcp[N];
inline void get_lcp()
{
	int k=0;
	for(int i=1;i<=n;++i)	rk[sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk[i]>1){
			if(k)	--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]){
				++k;
			}	
			lcp[rk[i]]=k;
		}
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	get_sa();
	get_lcp();
	for(int i=1;i<=n;++i){
		printf("%d ",sa[i]);
	}
	puts("");
	for(int i=2;i<=n;++i){
		printf("%d ",lcp[i]);
	}
	return 0;
}

新板子
hgt[i]表示排名i和排名i-1的后缀的lcp

倍增的排序用的是基数排序
基数排序的第一关键字用计数排序。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100008;
int n;
char s[N];
int sa[N],rk[N],sa2[N],cnt[N];
IL void get_sa()
{
	int *sa2=::sa2,*rk=::rk;
	int m=128;
	for(int i=1;i<=n;++i)	++cnt[rk[i]=s[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=1;i<=n;++i)	sa[++cnt[rk[i]-1]]=i;//sa[cnt[rk2[i]]--]=i;
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa2[++p]=sa[i]-k;
		
		for(int i=0;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk[i]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i>0;--i)	sa[cnt[rk[sa2[i]]]--]=sa2[i];
		//for(int i=1;i<=n;++i)	sa[++cnt[rk2[sa2[i]]-1]]=sa2[i];
		
		swap(sa2,rk);
		rk[sa[1]]=p=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&sa2[sa[i]]==sa2[sa[i-1]]&&sa2[sa[i]+k]==sa2[sa[i-1]+k]){
				rk[sa[i]]=p;
			}
			else{
				rk[sa[i]]=++p;
			}
		}
		if(p==n)	break;//!!
	}
}
int hgt[N];
IL void get_hgt()
{
	for(int i=1;i<=n;++i)	rk[sa[i]]=i;
	for(int i=1,k=0;i<=n;++i){
		if(rk[i]>1){
			if(k>0)	--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]){
				++k;
			}
			hgt[rk[i]]=k;
		}
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	get_sa();
	get_hgt();
	for(int i=1;i<=n;++i){
		printf("%d ",sa[i]);
	}
	putchar('\n');
	for(int i=2;i<=n;++i){
		printf("%d ",hgt[i]);
	}
	return 0;
}
int lg2[N],st[20][N];
for(int i=2;i<=n;++i){//在n输入之前的话要预处理到N
	lg2[i]=lg2[i>>1]+1;
}
IL void get_lcp()
{
	for(int i=2;i<=n;++i)	st[0][i]=hgt[i];
	for(int i=1;(1<<i)<n;++i){
		for(int j=2;j+(1<<i)-1<=n;++j){
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
		}
	}
}
IL int get_lcp(int x,int y)
{
	if(x==y)	return n-sa[x]+1;//求同一个后缀的lcp就是自身的长度
	if(x>y)	swap(x,y);++x;
	int t=lg2[y-x+1];
	return min(st[t][x],st[t][y-(1<<t)+1]);
}

hihocoder上有四道后缀数组经典应用题
hiho1403 后缀数组一·重复旋律 最长可重叠重复K次子串（单调队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=20008;
int n,k;
int s[N];
int sa[N],rk[N],lcp[N],a[N],b[N],cnt[N];
inline void get_sa()
{
	int m=100;
	int *rk_1=a,*sa_2=b,*tmp;
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
inline void get_lcp()
{
	int k=0;
	for(int i=1;i<=n;++i)	rk[sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk[i]>1){
			if(k)	--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]){
				++k;	
			}
			lcp[rk[i]]=k;
		}
	}
}
int q[N],he,ta;
int ans;
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;++i){
		s[i]=read();
	}
	if(k==1){
		printf("%d",n);
		return 0;
	}
	get_sa();
	get_lcp();
	--k;
	he=1;ta=0;
	for(int i=2;i<2+k;++i){
		while(he<=ta&&lcp[i]<=lcp[q[ta]]){
			--ta;
		}
		q[++ta]=i;
	}
	for(int i=2+k;i<=n;++i){
		while(he<=ta&&lcp[i]<=lcp[q[ta]]){
			--ta;
		}
		q[++ta]=i;
		if(i-q[he]>=k)	++he;
		ans=max(ans,lcp[q[he]]);
	}
	printf("%d",ans);
	return 0;
}

hiho1407 后缀数组二·重复旋律2 最长不可重叠重复子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008;
int n;
int s[N];
int sa[N],rk[N],lcp[N],a[N],b[N],cnt[N];
inline void get_sa()
{
	int m=1000;
	int *rk_1=a,*sa_2=b,*tmp;
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
inline void get_lcp()
{
	int k=0;
	for(int i=1;i<=n;++i)	rk[sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk[i]>1){
			if(k)	--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]){
				++k;
			}
			lcp[rk[i]]=k;
		}
	}
}
int l,r,mid,ans;
int mini,maxi;
inline bool ok()
{
	mini=sa[1];
	maxi=sa[1];
	for(int i=2;i<=n;++i){
		if(lcp[i]<mid){
			mini=sa[i];
			maxi=sa[i];
		}
		else{
			mini=min(mini,sa[i]);
			maxi=max(maxi,sa[i]);
			if(maxi-mini>=mid)	return 1;
		}
	}
	return 0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i){
		s[i]=read();
	}
	get_sa();
	get_lcp();
	l=0;r=n-1;
	while(l<=r){
		mid=(l+r)>>1;
		if(ok()){
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	printf("%d",ans);
	return 0;
}

hiho1415 后缀数组三·重复旋律3 最长公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=200008;
int n1,n;
char s[N];
int sa[N],rk[N],lcp[N],a[N],b[N],cnt[N];
inline void get_sa()
{
	int m=128;
	int *rk_1=a,*sa_2=b,*tmp;
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
inline void get_lcp()
{
	int k=0;
	for(int i=1;i<=n;++i)	rk[sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk[i]>1){
			if(k)	--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])	++k;
			lcp[rk[i]]=k;
		}
	}
}
int ans;
int main()
{
	scanf("%s",s+1);
	n1=strlen(s+1);
	s[n1+1]='#';
	scanf("%s",s+n1+2);
	n=strlen(s+1);
	get_sa();
	get_lcp();
	for(int i=2;i<=n;++i){
		if((sa[i-1]<=n1)^(sa[i]<=n1)){
			ans=max(ans,lcp[i]);
		}
	}
	printf("%d",ans);
	return 0;
}

hiho1419 后缀数组四·重复旋律4 重复次数最多的连续字串
错了好多次就是st_rev和st打错了
重写了一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008;
int n;
char s[N],s_rev[N];
int sa[N],rk[N],lcp[N],a[N],b[N],cnt[N];
inline void get_sa()
{
	int m=128;
	int *rk_1=a,*sa_2=b,*tmp;
	for(int i=1;i<=m;++i)	cnt[i]=0;
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
inline void get_lcp()
{
	int k=0;
	for(int i=1;i<=n;++i)	rk[sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk[i]>1){
			if(k)	--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])	++k;
			lcp[rk[i]]=k;
		}
	}
}
inline void get_sa_rev()
{
	int m=128;
	int *rk_1=a,*sa_2=b,*tmp;
	for(int i=1;i<=m;++i)	cnt[i]=0;
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s_rev[i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
int rk_rev[N],lcp_rev[N];
inline void get_lcp_rev()
{
	int k=0;
	for(int i=1;i<=n;++i)	rk_rev[sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk_rev[i]>1){
			if(k)	--k;
			int j=sa[rk_rev[i]-1];
			while(i+k<=n&&j+k<=n&&s_rev[i+k]==s_rev[j+k])	++k;
			lcp_rev[rk_rev[i]]=k;
		}
	}
}
int st[20][N],st_rev[20][N];
inline void get_st()
{
	for(int i=2;i<=n;++i){
		st[0][i]=lcp[i];
	}
	for(int i=1;(1<<i)<n;++i){
		for(int j=2;j+(1<<i)-1<=n;++j){
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]); 
		}
	}
}
inline void get_st_rev()
{
	for(int i=2;i<=n;++i){
		st_rev[0][i]=lcp_rev[i];
	}
	for(int i=1;(1<<i)<n;++i){
		for(int j=2;j+(1<<i)-1<=n;++j){
			st_rev[i][j]=min(st_rev[i-1][j],st_rev[i-1][j+(1<<(i-1))]);
		}
	}
}
inline int rmq(int x,int y)
{
	if(x>y)	swap(x,y);
	int t=log2(y-x);
	return min(st[t][x+1],st[t][y-(1<<t)+1]);
}
inline int rmq_rev(int x,int y)
{
	if(x>y)	swap(x,y);
	int t=log2(y-x);
	return min(st_rev[t][x+1],st_rev[t][y-(1<<t)+1]);
}
int x,y,ans;
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	get_sa();
	get_lcp();
	get_st();
	for(int i=1;i<=n;++i){
		s_rev[i]=s[n-i+1];
	}
	get_sa_rev();
	get_lcp_rev();
	get_st_rev();
	ans=1;
	for(int l=1;l<=n/2;++l){
		y=l;
		for(int i=1;i<n/l;++i){
			x=y;
			y+=l;
			ans=max(ans,(rmq(rk[x],rk[y])+rmq_rev(rk_rev[n-x+1],rk_rev[n-y+1])-1)/l+1);
		}
	}
	printf("%d\n",ans);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008;
int n;
char s[2][N];
int sa[N],rk[2][N],lcp[2][N],a[N],b[N],cnt[N];
inline void get_sa(int id)
{
	int m=128;
	int *rk_1=a,*sa_2=b,*tmp;
	for(int i=1;i<=m;++i)	cnt[i]=0;
	for(int i=1;i<=n;++i)	++cnt[rk_1[i]=s[id][i]];
	for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
	for(int i=n;i;--i)	sa[cnt[rk_1[i]]]=i,--cnt[rk_1[i]];
	
	for(int k=1,p;k<=n;k<<=1,m=p){
		p=0;
		for(int i=n-k+1;i<=n;++i)	sa_2[++p]=i;
		for(int i=1;i<=n;++i)	if(sa[i]>k)	sa_2[++p]=sa[i]-k;
		
		for(int i=1;i<=m;++i)	cnt[i]=0;
		for(int i=1;i<=n;++i)	++cnt[rk_1[sa_2[i]]];
		for(int i=1;i<=m;++i)	cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)	sa[cnt[rk_1[sa_2[i]]]]=sa_2[i],--cnt[rk_1[sa_2[i]]];
		
		tmp=sa_2;
		p=1;
		tmp[sa[1]]=1;
		for(int i=2;i<=n;++i){
			if(sa[i]+k<=n&&sa[i-1]+k<=n&&rk_1[sa[i]]==rk_1[sa[i-1]]&&rk_1[sa[i]+k]==rk_1[sa[i-1]+k]){
				tmp[sa[i]]=p;
			}
			else{
				tmp[sa[i]]=++p;
			}
		}	
		if(p==n)	break;
		swap(rk_1,sa_2);
	}
}
inline void get_lcp(int id)
{
	int k=0;
	for(int i=1;i<=n;++i)	rk[id][sa[i]]=i;
	for(int i=1;i<=n;++i){
		if(rk[id][i]){
			if(k)	--k;
			int j=sa[rk[id][i]-1];
			while(i+k<=n&&j+k<=n&&s[id][i+k]==s[id][j+k])	++k;
			lcp[id][rk[id][i]]=k;
		}
	}
}
int st[2][20][N];
inline void get_st(int id)
{
	for(int i=2;i<=n;++i){
		st[id][0][i]=lcp[id][i];
	}
	for(int i=1;(1<<i)<n;++i){
		for(int j=2;j+(1<<i)-1<=n;++j){
			st[id][i][j]=min(st[id][i-1][j],st[id][i-1][j+(1<<(i-1))]);
		}
	}
}
inline int rmq(int id,int x,int y)
{
	if(x>y)	swap(x,y);
	int t=log2(y-x);
	return min(st[id][t][x+1],st[id][t][y-(1<<t)+1]);
}
int x,y;
int ans;
int main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	scanf("%s",s[0]+1);
	n=strlen(s[0]+1);
	for(int i=1;i<=n;++i){
		s[1][i]=s[0][n-i+1];
	}
	get_sa(0);
	get_lcp(0);
	get_st(0);
	get_sa(1);
	get_lcp(1);
	get_st(1);
	ans=1;
	for(int l=1;l<=n/2;++l){
		y=l;
		for(int i=1;i<n/l;++i){
			x=y;
			y+=l;
			ans=max(ans,(rmq(0,rk[0][x],rk[0][y])+rmq(1,rk[1][n-x+1],rk[1][n-y+1])-1)/l+1);
		}
	}
	printf("%d",ans);
	return 0;
}