#2377. 「AHOI2013」差异

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

给定一个长度为 $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$ 。

一行，一个整数，表示所求值。

输入

ababc

输出

对于 $100\%$ 的数据， $2 \le n \le 500000$ 。