BZOJ3238: [Ahoi2013]差异

Time Limit: 20 Sec  Memory Limit: 512 MBDescription

Input

一行,一个字符串S

Output

 

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

Sample Input

cacao

Sample Output


54

HINT

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

Solution

要求任意两个后缀之间的LCP,也就是这两个后缀后缀排名后区间的height最小值,但这样处理非常麻烦。

我们考虑每个height对答案的贡献,可以用单调栈预处理出每个height对向左和向右多少后缀有影响(即是这一段的最小值)。

 

 

点赞

发表评论

您的电子邮箱地址不会被公开。