rt

## 思路

这道题我们可以先对字符串的所有后缀进行排序。那么答案肯定就是 $1\leq i\leq j\leq|s|$ 和 $1\leq k$ 了，也就是所有 $c_i\ldots j$ 中长度为 $k$ 的前缀相等的数量。如果 $i=j$，答案就是 $1\leq k\leq|c_i|$，也就是 $\dfrac{|s|\times (|s| + 1)}{2}$。然后让我们计算相邻后缀的最长公共子序列，也就是 $a_i=lcp(c_i,c_i+1)$。最后让我们计算 $1\leq i\leq j<|s|$ 和 $1\leq k$ ，也就是统计一下 $k\leq min(a[i][j])$ 的数量，输出结果就可以了。

思路

这道题我们可以先对字符串的所有后缀进行排序。那么答案肯定就是 $1\leq i\leq j\leq|s|$ 和 $1\leq k$ 了，也就是所有 $c_i\ldots j$ 中长度为 $k$ 的前缀相等的数量。如果 $i=j$，答案就是 $1\leq k\leq|c_i|$，也就是 $\dfrac{|s|\times (|s| + 1)}{2}$。然后让我们计算相邻后缀的最长公共子序列，也就是 $a_i=lcp(c_i,c_i+1)$。最后让我们计算 $1\leq i\leq j<|s|$ 和 $1\leq k$ ，也就是统计一下 $k\leq min(a[i][j])$ 的数量，输出结果就可以了。