A2575. 差异
编程题
省选/NOI-
知识点
题目描述
给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求
$$\displaystyle \sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$
其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。
$$\displaystyle \sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$
其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。
输入格式
一行，一个字符串 $S$。
输出格式
一行，一个整数，表示所求值。
输入输出样例
输入 #1
cacao
输出 #1
54
说明/提示
#### 数据规模与约定
- 对于 $100\%$ 的数据，保证 $2\le n\le 500000$，且 $S$ 中均为小写字母。
- 对于 $100\%$ 的数据，保证 $2\le n\le 500000$，且 $S$ 中均为小写字母。