CLICK HERE(LINK)

$\large\text{Outline}$

• 并查集可以较为方便地维护 $\text{Height}$ 数组的分组。

$\large\text{Algorithm}$

• 显然，如两后缀的 $\text{LCP}$ 长度大于等于 $r$，则它们一定满足 $r$ 相似。
• 根据 $\text{LCP Theorem}$，若 $\min_{k\in[\text{rank}_i+1,\text{rank}_j]}\text{Height}_k\geq r$，则 $\text{Suf(S,i)}$ 与 $\text{Suf(S,j)}$ 满足 $r$ 相似。
• 显然该条件具备传递性，即对于 $i<k<j$，若 $\text{Suf}(S,i)$ 与 $\text{Suf}(S,k)$ 满足 $r$ 相似，且 $\text{Suf}(S, j)$ 与 $\text{Suf}(S,k)$ 满足 $r$ 相似，则 $\text{Suf}(S,i)$ 与 $\text{Suf}(S,j)$ 满足 $r$ 相似。进一步延伸得左端点在区间 $[i,j]$ 内的所有后缀两两满足条件。
• 因此从大到小考虑 $r$，可以转化为区间与区间的集合合并问题，可使用并查集维护。

$\large\text{Notes}$

• 对于 $\text{LCP}$ 类问题，尤其是对于每一种长度均求解答案的 $\text{LCP}$ 问题，优先考虑对 $\text{Height}$ 数组进行分组。