#227. [AHOI2013] 差异

[AHOI2013] 差异

[AHOI2013] 差异

题目描述

给定一个长度为 nn 的字符串 SS,令 TiT_i 表示它从第 ii 个字符开始的后缀。求

$\displaystyle \sum_{1\leqslant i<j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$

其中,len(a)\text{len}(a) 表示字符串 aa 的长度,lcp(a,b)\text{lcp}(a,b) 表示字符串 aa 和字符串 bb 的最长公共前缀。

输入格式

一行,一个字符串 SS

输出格式

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

样例 #1

样例输入 #1

cacao

样例输出 #1

54

提示

数据规模与约定

  • 对于 100%100\% 的数据,保证 2n5000002\le n\le 500000,且 SS 中均为小写字母。