首先当然是对所有后缀进行排序，然后我们考虑二分答案，假设当前的长度是 $l$，那么我们可以把排好序的后缀分成几段，其中每一段的lcp(height)都是大于等于$l$的，于是我们记录一下每一段后缀中rl(sa)的最大值和最小值，如果最大值和最小值的差大于$l$，那么就说明有不重叠的重复子串，反之则不然，这样的做法是$O(n\log n)$的。当然，我们还可以有$O(n)$的做法，在尺取的同时，用单调队列维护一下rl(sa)的最大值和最小值，并且答案就是所有符合条件的lcp(height)的最大值。

首先可以用同上题的做法，二分答案$l$，对于lcp(height)大于等于$l$的每一段，看看是否长度超过$k$，同样，这个方法的复杂度是$O(n\log n)$的。但是我们可以发现，用尺取，每次取长度为$k$的一段，同样可以把复杂度优化到$O(n)$。

我们可以发现，对于后缀排序是$i$的后缀，以rl[i](sa[i])作为开头，并且以lcp[i](height[i])及其之前最为结尾的所有子串都会被重复计算，于是我们就不去记这一段对答案的贡献，于是我们所要求的答案就是$\displaystyle\sum_{i=1}^nn-rl[i]+1-lcp[i]$，显然这样的做法的复杂度是$O(n)$的。

我们考虑把一整个字符串复制一段并且翻转，接在原字符串的后面，中间用一个没出现过的字符连接，然后我们对这个新的字符串进行后缀排序，于是我们可以通过枚举中心节点来更新答案，其中中心节点需要根据长度的奇偶性来分类枚举，由于$ST$表预处理的复杂度是$O(n\log n)$的，所以这个做法的整体复杂度也是$O(n\log n)$的。当然，如果能够把$RMQ$的复杂度降为$O(1)$，那么就可以把整体复杂度降到$O(n)$，具体的话就是笛卡尔树＋$Tarjan$。

通过观察可以发现，如果一个串的连续重复子串的长度为$l$，那么有串$s[1]$和$s[l+1]$的$lcp$等于$n-l$，所以就只需要枚举一下总长度的因子就行，然后$lcp$可以用$ST$表求得，这样做的复杂度是$O(n\log n)$的。当然还能进行优化，由于$RMQ$的一端是固定的，于是可以用一个数组$O(n)$处理，这样就可以把复杂度降到$O(n)$。

我们考虑枚举长度$l$为重复周期，那么就可以发现$s[1],s[1+l],\cdots,s[1+x\times l]$一定会在一个连续重复子串中，于是对于$s[1+a\times l]$和$s[1+a\times l+l]$，他们的$lcp$就是最长能往后延伸的长度，如果$lcp$不能被$l$整除，就看看能否往前再延伸一小段距离使得当前的答案增加一，然后算一下复杂度是$\displaystyle O\left(\sum_{i=1}^n{n\over i}\right)$即$O(n\log n)$的。

我们考虑把两段用一个没出想过的字符连起来，把这个新的字符串进行后缀排序。可以发现，最长公共子串一定出现在相邻两串的$lcp$中，这样的复杂度是$O(n)$的。

我们先按之前的方法连接字符串并且进行后缀排序，然后对于两个位于不同串的后缀，他们对答案的贡献很好处理，但是有这么多后缀，于是考虑怎么优化。我们首先对于每一个串$B$的后缀，计算它与它之前出现过的串$A$的后缀对答案的贡献，然后对串$A$也是同样，同时我们可以用一个单调栈进行优化，这样的复杂度是$O(n)$的。

我们先把所有串都连在一起，并且中间用没出现过的并且互不相同的字符相连，然后对新串进行后缀排序，然后同样我们可以二分长度$l$，对于lcp大于等于$l$的每一段，看是否出现在不少于$k$个串中，这样的复杂度是$O(n\log n)$的，当然可以参照之前的方法，用尺取＋单调队列把复杂度优化到$O(n)$。

先像之前那样构造新串并进行后缀排序，然后二分答案$l$，对于lcp大于等于$l$的每一段，记录在每个串中rl的最大值和最小值，并进行判断即可，这样的复杂度是$O(n\log n)$的。

把每个串都复制一遍并翻转然后用$2\times n$个没出现过的且互不相同的字符连接这些字符串，再把新串进行后缀排序，二分长度$l$，对于lcp大于等于$l$的每一段，看是否在每个串中都出现过，这样的复杂度同样也是$O(n\log n)$的。