P2414 [NOI2011]阿狸的打字机[AC自动机]

题目背景

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。

题目描述

打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现,这个打字机是这样工作的:

·输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
·按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。
·按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

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

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

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

输入输出格式

输入格式:

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

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

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

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
5
aPaPBbP
3
1 2
1 3
2 3

输出样例#1:

1
2
3
2
1
0

说明

数据范围:

对于100%的数据,n<=100000,m<=100000,第一行总长度<=100000。

img

题解

设我们要查串x在串y中的出现次数

相当于查y中有多少个点,沿着fail走,可以走到x的结束点。

我们可以建一棵fail树,

0->y这条路径上有多少个点,在fail树上是x的结束点 的子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(isdigit(s))
{
k=k*10+(s^'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=1e5+2;
char Ch[maxn];
int t[maxn][26];
int End[maxn],fail[maxn],Fa[maxn];
int Now,id1,n,word,Map[maxn];//trie
inline void ac_add(int x)
{
if (t[Now][x]==0)
{
t[Now][x]=++id1;
Fa[id1]=Now;
}
Now=t[Now][x];
}
int ans[maxn],m;//答案
int id,to[maxn<<1],ne[maxn<<1],po[maxn];//fail树
int Id,to1[maxn],ne1[maxn],po1[maxn],num[maxn];//询问
inline void add1(int x,int y,int ID)
{
Id++;
to1[Id]=y;
num[Id]=ID;
ne1[Id]=po1[x];
po1[x]=Id;
}
inline void add(int x,int y)
{
id++;to[id]=y;ne[id]=po[x];po[x]=id;
}
inline void get_fail()
{
queue<int> q;
while (!q.empty()) q.pop();
for (int i=0;i<26;i++)
{
if (t[0][i]!=0)
{
fail[t[0][i]]=0;
q.push(t[0][i]);
}
}

while (!q.empty())
{
int u=q.front();q.pop();
for (int i=0;i<26;i++)
{
if (t[u][i]!=0)
{
fail[t[u][i]]=t[fail[u]][i];
q.push(t[u][i]);
} else t[u][i]=t[fail[u]][i];
}
}

for (int i=1;i<=n;i++)
{
add(i,fail[i]);
add(fail[i],i);
}
}
int dfn[maxn],sz[maxn],dfs_time;
void dfsfail(int x,int Fa)//遍历fail树
{
dfn[x]=++dfs_time;
sz[x]=1;
for (int i=po[x];i;i=ne[i])
{
if (to[i]!=Fa)
{
dfsfail(to[i],x);
sz[x]+=sz[to[i]];
}
}
}
int a[maxn];
inline void xg(int x,int y)
{
while (x<=n+1)
{
a[x]+=y;
x+=x&(-x);
}
}
inline int qsum(int x)
{
int ss=0;
while (x)
{
ss+=a[x];
x-=x&(-x);
}
return ss;
}
void dfs(int x)//trie树
{
xg(dfn[x],1);
int y;
for (int i=po1[x];i;i=ne1[i])//查询串以x点为结束点的询问
{
y=to1[i];
ans[num[i]]=qsum(dfn[y]+sz[y]-1)-qsum(dfn[y]-1);
}
for (int i=0;i<26;i++)
{
if (t[x][i]!=0&&Fa[t[x][i]]==x)
{
dfs(t[x][i]);
}
}
xg(dfn[x],-1);
}
int main()
{
scanf("%s",Ch+1);
n=strlen(Ch+1);
for (int i=1;i<=n;i++)
{
if (Ch[i]=='B')
{
Now=Fa[Now];
} else
if (Ch[i]=='P')
{
End[Now]=++word;
Map[word]=Now;
} else ac_add(Ch[i]-'a');
}
int X,Y;
m=read();
for (int i=1;i<=m;i++)
{
X=read();Y=read();
add1(Map[Y],Map[X],i);
}
n=id1;//总节点数
get_fail(); //求fail
dfsfail(0,-1);//建fail树
dfs(0);//扫trie树
for (int i=1;i<=m;i++) write(ans[i]),putchar('\n');
return 0;
}