BZOJ 2434: [Noi2011]阿狸的打字机(AC自动机+fail树)

Description

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。

经阿狸研究发现,这个打字机是这样工作的:

l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。

l 按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Input

输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m,表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。

Output

输出m行,其中第i行包含一个整数,表示第i个询问的答案。

Sample Input

aPaPBbP

3

1 2

1 3

2 3

Sample Output

2

1

0
HINT

1<=N<=10^5 1<=M<=10^5 输入总长<=10^5 经典题目吧。 通过AC自动机建出fail树后,我们可以知道如果一个v的父亲节点为u,那也就意味着u所代表的字符串是v的后缀,也就是u在v出现了一次。所以我们只需要统计一个字符串v中的每个节点(从root->v的末尾),通过fail指针能走到u有几个就可以了。但是这显然可以被卡到n*len的。。。
其实建立出来fail树之后,可以通过dfs序来确定出来u的范围,我们只需要统计这个子树范围内有多少个属于u的节点即可。因为这个题目具有特殊性质,在不使用B的话前缀是一直累加的。那么我们离线询问,然后对于每个字符串末尾结点,统计一下这个时候它的节点在哪些询问的u的子树内。这个用树状数组即可。所以我们只用重新在走一遍AC自动机的建立过程就可以统计出来所有答案了。复杂度就是O(n+mlogn)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注