「BZOJ3238」[Ahoi2013] 差异

2015年4月9日4,2816

Description

Input

一行,一个字符串S

Output

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

Sample Input

cacao

Sample Output

54

HINT

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

显然后缀数组不是正确姿势。。。

不过还是说说后缀数组的做法吧,bzoj总时限20s是能过的

SA+rmq求lcp应该烂大街了,这题还不用rmq。。。

首先求出h数组

考虑h[i]在哪些区间内会成为最小值,这个用两次单调栈很容易就能解决

还要处理一下由于h[i]可能相同造成的重复计数问题,具体看代码

 

 

说点什么

提醒
avatar
De℃,.: )
De℃,.: )

跪·什么是正确姿势?

xdj's friend
xdj's friend

XDJ!!

ydc
ydc

后缀数组为何不是正确姿势

ydc
ydc

擦,头像是默认的么,遭不住啊