首页 > 题解 > bzoj 3238 [Ahoi2013]差异

bzoj 3238 [Ahoi2013]差异

Description

Input

一行,一个字符串S

Output

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

Sample Input

cacao

Sample Output

54

HINT

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

题解

反串的parent树是原串的后缀树

然后lcp就是他们的lca的深度,然后树形DP一下就好了

其实可以不用重建树直接拓扑排序,我这么写改了一上午也不对,拍了有2个小时。。于是直接重建了个树,神清气爽一遍A


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×