#227. [AHOI2013] 差异
[AHOI2013] 差异
[AHOI2013] 差异
题目描述
给定一个长度为 的字符串 ,令 表示它从第 个字符开始的后缀。求
$\displaystyle \sum_{1\leqslant i<j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$
其中, 表示字符串 的长度, 表示字符串 和字符串 的最长公共前缀。
输入格式
一行,一个字符串 。
输出格式
一行,一个整数,表示所求值。
样例 #1
样例输入 #1
cacao
样例输出 #1
54
提示
数据规模与约定
- 对于 的数据,保证 ,且 中均为小写字母。