AC. 梦想

frank_c1

[SDOI 2016] 生成魔咒

发布于2016年04月23日 | 暂无评论 | 861阅读 | 后缀自动机

题目描述

魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符1,2拼接起来形成一个魔咒串[1,2]

一个魔咒串S的非空子串被称为魔咒串S的生成魔咒。

例如S=[1,2,1]时,它的生成魔咒有[1],[2],[1,2],[2,1],[1,2,1]五种。S=[1,1,1]时,它的生成魔咒有[1],[1,1],[1,1,1]三种。最初S为空串。共进行n次操作,每次操作是在S的结尾加入一个魔咒字符。

每次操作后都需要求出,当前的魔咒串S共有多少种生成魔咒。

输入格式

第一行一个整数n

第二行n个数,第i个数表示第i次操作加入的魔咒字符。

输出格式

输出n行,每行一个数。第i行的数表示第i次操作后S的生成魔咒数量。

题目解析

首先后缀自动机中结点所代表的子串不会有重复。考虑每一个非虚结点x,因为它所代表的串长度区间为[Max(fa(x))+1,Max(x)],所以它对答案的贡献就是len(x) - len(fa(x))。每次新建结点时计算一下就好。

字符集比较大,可以用map解决。时间复杂度O(n \log n)