[洛谷 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; }
发表评论