[AHOI2013] 差异 - Luogu - 题目详情 - 云斗学院

ID: 3176

远端评测题

2000ms

500MiB

难度: 6

上传者:

标签>

2013

各省省选

安徽

后缀自动机,SAM

后缀数组,SA

后缀树

题目描述

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 500000$ ，且 $S$ 中均为小写字母。