#P3238. [Ahoi2013]差异

    ID: 2423 传统题 1000ms 512MiB 尝试: 5178 已通过: 1558 难度: 7 上传者: 标签>CF2200提高+/省选-后缀数组倍增计数排序Kasai 算法单调栈单调栈计算区间贡献贡献法

[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。

输出格式

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

cacao
54

数据规模与约定

  • 对于 100%100\% 的数据,保证 2≤n≤5×1052 \leq n \leq 5 \times 10^5,且 SS 中均为小写字母。

题目来源

没有写明来源