LibreOJ
2377 「AHOI2013」差异
内存限制：512 MB
时间限制：1000 ms
题目描述
给定一个长度为 $n$ 的字符串 $S$ ，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀，求： $$\sum_{1 \le i < j \le n} \operatorname{len}(T_i)+\operatorname{len}(T_j)-2\operatorname{lcp}(T_i,T_j)$$
输入格式
一行，一个字符串 $S$ 。
输出格式
一行，一个整数，表示所求值。
样例
数据范围与提示
对于 $100\%$ 的数据， $2 \le n \le 500000$。
样例
样例输入 1
ababc
样例输出 1
54
LibreOJ