[BZOJ2434/Luogu2414][NOI2011]阿狸的打字机(AC自动机,dfs序,树状数组)

发布于 2018-03-20  7 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2434/Luogu2414][NOI2011]阿狸的打字机(AC自动机,dfs序,树状数组)

Description

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现,这个打字机是这样工作的:
l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。
例如,阿狸输入aPaPBbP,纸上被打印的字符如下:
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Tag

AC自动机,dfs序,树状数组

解决思路

首先,给出的操作可以构造出一棵包含所有我们需要的字符串的Trie树,在这棵Trie上构建AC自动机,考虑如何统计答案。
考虑在 AC 自动机中如何求得一个字符串在另一个中的出现次数(注意两个字符串都是 AC 自动机中的串)。可以发现,从串 y 在 Trie 中的每一个节点出发,若能从一个节点一直跳 Fail 跳到 x 串的末尾,那么 x 就在 y 中出现了一次。这提示我们统计答案似乎与 Fail 树有关,所以我们不妨把 Fail 树提出来。
把 Fail 树提出来后有什么用呢?我们再来看一看这时答案变成了什么。
对于要求 x 在 y 中出现了多少次,那么在 Fail 树中就是 y 串有多少个节点在x 串末尾节点的 fail 树的子树内(想一想为什么)。
于是我们呢就得到了更优的算法,即对于每一个询问 x,y,我们标记出 y 串的每一个节点,然后统计有多少个节点在 x 末尾节点的子树内。子树统计可以用dfs 序做到 O(1) 地统计。
但是这样还是不够,所以我们考虑把询问离线下来,当我们扫到一个字符串末尾的时候,一起回答它的所有询问。那这个扫的顺序如何确定呢?不妨再把之前构 Trie 树的操作再做一边。
这样一边走一边在 dfs 序中单点修改一个值,遇到结尾则查询,回答所有询问。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2434/Luogu2414][NOI2011]阿狸的打字机(AC自动机,dfs序,树状数组)


HNCJ OIer 一枚