隐藏
「NOI2011」阿狸的打字机 - AC自动机+树状数组 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「NOI2011」阿狸的打字机 - AC自动机+树状数组

题目大意

    给出一些字符串,询问第$x$个字符串在第$y$个字符串中出现的次数。


题目分析

因为本题的特殊输入方式,搞出所有的字符串会TLE。
所以不妨沿着转移边走,遇到$B$返回父节点,遇到$P$标记结束位置。

现在考虑如何统计第$x$个字符串在$y$中出现的次数。
若存在一个包含$x$的极短串$z$,那么一定有$z$的$fail$指针指向$x$,且存在对于包含$z$的串$z’$,若$z’$不存在其它位置包含$x$,那么$z’$的$fail$指针一定不指向$x$。
考虑到$fail$指针的这一个性质,题目的要求便转化为了:
在以$x$为根的$fail$子树中,存在多少个$y$字符串上的结点。

这样我们可以将所有$y$字符串上的结点记为$1$,在$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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=200005;

struct Query {
int x,id;
};

int n,m,num=0,step=0,pos[maxn],First[maxn],Last[maxn],Ans[maxn];
vector<int>edges[maxn];
vector<Query>q[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

struct BIT {
int c[maxn];
#define lowbit(x) x&-x
void add(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} bit;

struct Aho_Corasick_Automaton {
struct Tree {
int child[26],fail,fa;
int cnt,id;
} tree[maxn];
int root,cnt;
#define ch(x,i) tree[x].child[i]
#define fail(x) tree[x].fail

Aho_Corasick_Automaton() {
init();
}

void init() {
root=cnt=1;
memset(tree,0,sizeof(tree));
}

int insert(string s) {
int now=root;
for(int i=0; i<s.length(); i++) {
int j=s[i]-'a';
if(!ch(now,j))ch(now,j)=++cnt;
now=ch(now,j);
}
tree[now].cnt++;
return now;
}

void build(string s) {
int now=root;
for(auto x:s) {
if(x=='P') {
tree[now].id=++num;
pos[num]=now;
} else if(x=='B')now=tree[now].fa;
else {
int j=x-'a';
if(!tree[now].child[j])tree[now].child[j]=++cnt,tree[cnt].fa=now;
now=ch(now,j);
}
}
}

void buildfail() {
queue<int>Q;
Q.push(root);
while(!Q.empty()) {
int now=Q.front();
AddEdge(tree[now].fail,now);
Q.pop();
for(int i=0; i<26; i++) {
int& next=ch(now,i);
if(!next) {
next=ch(fail(now),i)?ch(fail(now),i):root;
continue;
}
Q.push(next);
int p=fail(now);
while(p&&!ch(p,i))p=fail(p);
if(p)fail(next)=ch(p,i);
else fail(next)=root;
}
}
}

void dfs(int now) {
First[now]=++step;
for(int next:edges[now])dfs(next);
Last[now]=step;
}

void query(string s) {
int now=root;
for(auto c:s) {
if(c=='P') {
int y=tree[now].id;
for(auto Q:q[y])Ans[Q.id]=bit.sum(Last[pos[Q.x]])-bit.sum(First[pos[Q.x]]-1);
} else if(c=='B') {
bit.add(First[now],-1);
now=tree[now].fa;
} else {
now=ch(now,c-'a');
bit.add(First[now],1);
}
}
}
} ac;

char s[maxn];

int main() {
scanf("%s",s);
n=strlen(s);
ac.build(s);
ac.buildfail();
ac.dfs(1);
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
q[y].push_back((Query) {x,i});
}
ac.query(s);
for(int i=1; i<=m; i++)printf("%d\n",Ans[i]);
return 0;
}
姥爷们赏瓶冰阔落吧~