【bzoj3238】[Ahoi2013]差异

2015.04.14 18:46 Tue | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

.jpg)

Input

一行,一个字符串S

Output

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

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成

题解

求出后缀数组和height数组之后,正向反向分别搞一个单调栈求出每个h[i]所能管辖的最左段和最右端,然后用所有字串长度减去每个每个h[i]的左右乘积*2就行了。
最近一天敲一遍这道题的后缀数组,感觉写法很好,拜hzwer