← 返回题目
题库练习 差异
← 上一题 下一题 →

A2575 | 差异

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个长度为 $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$ 的最长公共前缀。

输入格式

一行，一个字符串 $S$。

输出格式

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

输入输出样例

输入 #1
cacao
输出 #1
54
C++ 编辑器
输入
输出