【bzoj3238】[Ahoi2013]差异

2015年4月9日3,3996

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]可能相同造成的重复计数问题,具体看代码

 

 

  • ydc2015年4月10日 下午5:17 回复

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

    #1  
    • ydc2015年4月10日 下午5:18 回复

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

      #11
      • hzwer2015年4月10日 下午9:35 回复
        admin

        据出题人说是想让大家后缀自动机平衡树什么的。。。。您的id。ydc?

        #12
      • hzwer2015年4月10日 下午9:37 回复
        admin

        您看这数据范围

        #12
  • De℃,.: )2015年4月10日 下午9:40 回复

    跪·什么是正确姿势?

    #2  
    • xdj's friend2015年4月13日 下午10:08 回复

      XDJ!!

      #21