问题引入
现在要求一个字符串中至少出现(k)次（可以重叠）的子串的最大长度。
问题解决
暴力
首先我们可以暴力找一个子串，暴力判断这个子串出现次数，暴力计算，这样子复杂度是(Theta(n^3))的。
SA
考虑一种全新的做法，后缀数组。
定义
(rnk_i)表示第(i)个后缀按照字典序排名为(rnk_i)
(sa_i)表示按照字典序排名为(i)的后缀是(sa_i)
(height_i)表示(sa_i)和(sa_i-1)的(LCP)（最长公共前缀）
求法
考虑倍增求解，当前如果解决了长度为(len)的然后准备扩展到(len*2)，那么显然需要把后缀补上然后再算前面算好了的。
这个具体的实现就是两个桶然后桶排。（可以参考代码）
代码实现
后缀数组的代码还是挺好记的（容易理解+1）
void get_sa(){
int m=100;
for(int i=1;i<=m;i++)t[i]=0;
for(int i=1;i<=n;i++)t[x[i]=a[i]]++;
for(int i=1;i<=m;i++)t[i]+=t[i-1];
for(int i=n;i;i--)sa[t[x[i]]--]=i;
int p=0;
for(int lim=1;p<=n && lim<=n;lim<<=1){
p=0;
for(int i=n-lim+1;i<=n;i++)y[++p]=i;
for(int i=1;i<=n;i++)if(sa[i]>lim)y[++p]=sa[i]-lim;
for(int i=1;i<=m;i++)t[i]=0;
for(int i=1;i<=n;i++)t[x[y[i]]]++;
for(int i=1;i<=m;i++)t[i]+=t[i-1];
for(int i=n;i;i--)sa[t[x[y[i]]]--]=y[i];
swap(x,y);x[sa[1]]=1;p=2;
for(int i=2;i<=n;i++)x[sa[i]]=cmp(sa[i],sa[i-1],lim)?p-1:p++;
m=p;
}
for(int i=1;i<=n;i++)rnk[sa[i]]=i;
for(int i=1,j=0;i<=n;i++){
j=max(0,j-1);int lst=sa[rnk[i]-1];
while(a[i+j]==a[lst+j])j++;
height[rnk[i]]=j;
}
}
例题
Problem A
Solution A
就是后缀数组的模板，如何判断最长长度？二分答案即可。
Problem B
Solution B
考虑两个后缀的(lcp)的长度，如果(ge mid)且这两个后缀之间的长度也(ge mid)那么显然就是一种可行的对吧。
然后直接二分答案然后判断即可，相当于是按照(height)分组。
Problem C
Solution C
显然可以把两个串拼起来，然后只需要判断两个相邻的后缀是否属于不同的串然后取(max_{i=1}^nheight_i)即可。
Problem D
Solution D
可以说是这四道题目里面最难的一道题目了（毕竟是4）
考虑枚举长度和起始位置，这样子是(Theta(n^2))的。
如何优化？显然可以只枚举(i-1)是(l)的倍数的位置，因为如果长度是(l)但不在(i)起始，显然会有一段多出来的接在后面，直接再求一次(lcp)取(max)即可。