hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4622

题意:

给一个字符串,给出若干询问,每组询问给一个区间[l,r],问区间中本质不同的字符串的个数。

思路:

观察发现,有10000组查询,字符串的长度最多才2000,所以可以预处理一波。

我们先考虑如何处理整个区间中,本质不同的子串数量。

考虑SAM,由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串,同时后缀自动机是最简的,所以问题也就变成了从初始状态开始不同路径的数量

每个节点 u 表示的子串长度在 [min[u],max[u]]范围内.

又由于max(u.fail) = min(u)-1

因此u表示的子串的长度就是变成了(max[u.fail],max[u] ]  (注意区间,是左闭右开)

由于每个长度的串都出现了一次,因此这个状态子串的个数就是max[u] – max[u.fail]

如果是统计整个串的本质不同的串的个数,那么buildSAM之后统计一下就行了。

现在是询问区间。

问题变成了,从[l,r]到[l,r+1],答案的改变是什么。

在SAM上添加一个字符之后,SAM当前的状态变成了cur,那么实际上,对答案的贡献,就是初始状态到新的状态cur的不同路径数目。

也就是max[cur]-max[cur.fail]

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz