[洛谷 2414][NOI2011] 阿狸的打字机【AC自动机(fail树)+树状数组】

  • 2018-02-28
  • 0
  • 0

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个询问的答案。

输入输出样例

输入样例#1:

aPaPBbP
3
1 2
1 3
2 3
输出样例#1:

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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai