[洛谷 2414][NOI2011] 阿狸的打字机【AC自动机(fail树)+树状数组】
Problem:
题目背景
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。
题目描述
打字机上只有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个询问的答案。
输入输出样例
aPaPBbP 3 1 2 1 3 2 3
2 1 0
说明
数据范围:
对于100%的数据，n<=100000,m<=100000,第一行总长度<=100000。
Solution:
本题是较难的 AC 自动机应用，涉及到了 fail 树的性质。
首先，由于输入字符串明显可以构成树形结构，所以我们可以直接模拟建 Trie。
设 Trie 上第 i 个串的结尾为 pos[i]，则求第 x 个串在第 y 个串中出现次数等价于求 root → pos[y] 的路径上所有节点沿 fail 指针能走到 pos[x] 的个数。
这样直接模拟的复杂度显然无法承受，我们可以引入 AC 自动机附带的一个数据结构 —— fail 树。
fail 树是将 AC 自动机上的 fail 指针反向建成的树，直接模拟建立即可。
那么原问题等价于求 AC 自动机 root → pos[y] 的路径上有多少节点在 fail 树 pos[x] 的子树内。
而子树在 DFS 序上是一个连续的区间，所以每次询问可以转化为区间求和的询问。
而路径上节点的贡献也可以看作一次单点加，边走 AC 自动机边维护即可。
单点加区间求和可以用树状数组简单实现。
Code: O(mlogm+(m+n)logn), n为串长 [12222K, 196MS]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, pair<int, int> > PII;
inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}
char opt[100002];
int m, len, tops = 0, pos[100002], ans[100002];
PII qr[100002];
#define y first
#define x second.first
#define id second.second
struct AC_Automaton{
int trie[100002][26], fa[100002], fail[100002], topp;
int q[100002], fr, re;
inline void init(char *str, int len){
int cur = 0, curid = 0;
for(register int i = 0; i < len; i++){
if(str[i] == 'P') pos[++curid] = cur;
else if(str[i] == 'B') cur = fa[cur];
else{
int v = str[i] - 'a';
if(!trie[cur][v]) trie[cur][v] = ++topp, fa[topp] = cur;
cur = trie[cur][v];
}
}
}
inline void build_fail(){
for(register int i = 0; i < 26; i++) if(trie[0][i]) fail[trie[0][i]] = 0, q[re++] = trie[0][i];
while(fr != re){
int u = q[fr++];
for(register int i = 0; i < 26; i++)
if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], q[re++] = trie[u][i];
else trie[u][i] = trie[fail[u]][i];
}
}
} AC;
// Aho-Corasick Automaton
struct Edge{
int np;
Edge *nxt;
};
struct Fail_Tree{
Edge *V[100002], E[100002];
int tope;
inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];}
inline void build(AC_Automaton &AC) {for(register int i = 1; i <= AC.topp; i++) addedge(AC.fail[i], i);}
} fail;
// Fail Tree of AC Automaton
int L[100002], R[100002], dfstime = 0;
inline void dfs(int u){
L[u] = ++dfstime;
for(register Edge *ne = fail.V[u]; ne; ne = ne->nxt) dfs(ne->np);
R[u] = ++dfstime;
}
// DFS Sequence
struct BIT{
int node[200002];
inline void add(int u, int v) {while(u < 200002) node[u] += v, u += u & -u;}
inline int query(int u) {int res = 0; while(u) res += node[u], u -= u & -u; return res;}
inline int query(int l, int r) {return query(r) - query(l - 1);}
} b;
// Binary Indexed Tree
int main(){
scanf("%s", opt), len = strlen(opt), AC.init(opt, len), AC.build_fail();
fail.build(AC), dfs(0);
getint(m);
for(register int i = 1; i <= m; i++) getint(qr[i].x), getint(qr[i].y), qr[i].id = i;
sort(qr + 1, qr + m + 1);
for(register int i = 0, cur = 0, curid = 0, curqr = 1; i < len; i++){
if(opt[i] == 'P'){
curid++;
while(curid == qr[curqr].y){
ans[qr[curqr].id] = b.query(L[pos[qr[curqr].x]], R[pos[qr[curqr].x]]);
curqr++;
}
}
else if(opt[i] == 'B') b.add(L[cur], -1), cur = AC.fa[cur];
else cur = AC.trie[cur][opt[i] - 'a'], b.add(L[cur], 1);
}
for(register int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
发表评论