AC. 梦想

frank_c1

[BZOJ 2780] Sevenk Love Oimaster

发布于2016年02月09日 | 1条评论 | 577阅读 | 后缀自动机,树状数组

题意简述

给定n(n<=10000)个模板串和q(q<=60000)个询问串,求每个询问串是多少个模板串的子串。

模板串总长不超过100000,询问串总长不超过360000。

题目解析

初学后缀自动机,第一题~~ 然而看了题解才明白。

首先对n个串构造广义后缀自动机。所谓广义后缀自动机,就是内含多个串的后缀自动机。此时某个结点不一定只属于某一个串,所以我们要在结点上用链表记录对应的是哪几个串。注意在读入新的串时把last置为root,然后按常规方法建立即可。

建好后缀自动机,把q个询问串放上去跑。设ST(a)为root接收字符串a所到达的状态,那么我们要求的就是以ST(a)为根的Parent子树中所有结点总共对应多少不同的模板串,直接做复杂度还是挺高的。建出Parent树,求出dfs序,那么问题可以转化成求一段连续序列中有多少个不同的数。用树状数组可以较快求出问题的答案。

另外这道题没有限定字符串由小写字母组成,所以字符集比较大,只能用map啦。

  • anonymous

    好劲啊拿这道题入门TAT