[NOI2011] 阿狸的打字机

[NOI2011] 阿狸的打字机

题目描述

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 B、P 两个字母。经阿狸研究发现，这个打字机是这样工作的：

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

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

a
aa
ab
1
2
3

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

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

题解

今天才发现以前学的的ac自动机是假的。
这道题我们直接按照按照last数组（fail的优化）往上跳，可以90point。
不过数据是真的水

inline void add(int x,int y,int id){
	++tot;
	to1[tot]=y; to2[tot]=id; nex[tot]=head[x]; head[x]=tot;
}
inline void add1(int x,int y){
	to[++hh]=y; ne[tot]=he[x]; he[x]=hh;  //ne也用的tot
}
1
2
3
4
5
6
7

这样居然可以90？？？

说说正解
先说说正确的ac自动机姿势

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1\sim n}$，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

假设我们当前在ac自动机上走到now这个点，那么一个显然的想法就是沿着fail链往上跳，然后所有走到的点（字符串结尾）+1。

设$fail[x]=y$
反过来想，如果我们将y连向x，那么这个关系将会构成一颗树，我们只需要将字符串到过的点打个标记，最后求一遍子树和即可。

#include
#include
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=2e6+5;
int ch[N][26],fa[N],now,cnt,l,n,c,val[N],mat[N];
char s[N];
int h,t,q[N],r,u,v,f[N];
int head[N],to[N],nex[N],tot,sum[N];
void ins(int x){
	now=0;
	fo(i,1,l){
		c=s[i]-'a';
		if (!ch[now][c]) ch[now][c]=++cnt;
		now=ch[now][c];
	}
	mat[x]=now;
}
void build(){
	h=t=0;
	fo(i,0,25) if (ch[0][i]) q[++t]=ch[0][i];
	while (h<t){
		r=q[++h];
		fo(i,0,25){
			u=ch[r][i];
			if (!u) {
				ch[r][i]=ch[f[r]][i];//与下一个代码有区别
				continue; 
			}
			v=f[r];
			while (v && !ch[v][i]) v=f[v];
			f[u]=ch[v][i];
			q[++t]=u;
		}
	}
}
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		dfs(v);
		sum[x]+=sum[v];
	}
}
int main(){
//	freopen("data.in","r",stdin);
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%s",s+1);
		l=strlen(s+1);

		ins(i);
	}
	build();
	scanf("%s",s+1);
	l=strlen(s+1);
	
	now=0;
	
	fo(i,1,l) {
		c=s[i]-'a';
		now=ch[now][c];
		sum[now]++;
	}
	
	fo(i,1,cnt) add(f[i],i);
	dfs(0);
	
	fo(i,1,n) {
		printf("%d\n",sum[mat[i]]);
	}
	return 0;
} 
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

那么这个题其实也差不多。
首先建好树后先得到dfs序，一个字树的dfs序肯定是一段连续的区间。我们只需要dfs的时候修改即可。

#include
#include
#include
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e5+1000;
int ch[N][26];
char s[N];
int n,m,x,y,now,l,c,cnt;
int f[N],fa,val[N],sum;
int h,t,q[N],r,u,v,ans[N],d[N],Fa[N],wh[N],dep;
bool vis[N];
int to[N],ne[N],head[N],hh;
int nex[N],to1[N],to2[N],he[N],tot;
int e[N],st[N],top,k;
int To[N],num,Nex[N],last[N];
int dfn[N],zz;
int li[N],ri[N];
int ss[N];
int lowbit(int x){
	return (x&(-x));
}
void update(int x,int y){
	while (x<N){
		ss[x]+=y;
		x+=lowbit(x);
	}
}
int ask(int x){
	int s=0;
	while (x){
		s+=ss[x];
		x-=lowbit(x);
	}
	return s;

}

inline void add(int x,int y,int id){
	++tot;
	to1[tot]=y; to2[tot]=id; nex[tot]=head[x]; head[x]=tot;
}
inline void add1(int x,int y){
	to[++hh]=y; ne[hh]=he[x]; he[x]=hh;
}
void add2(int x,int y){
	To[++num]=y; Nex[num]=last[x]; last[x]=num;
}
inline void R(int &x){
	int t=0; char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for (;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
void work(){
	now=0;  dep=0;
	
	l=strlen(s+1); 
	fo(i,1,l) {
		if ('a'<=s[i] && s[i]<='z') {
			fa=now;
			dep++;
			
			c=s[i]-'a';
			if (!ch[now][c]) ch[now][c]=++cnt; 
			now=ch[now][c] ; 
			
			Fa[now]=fa;
			
		}
		if (s[i]=='B') {
			dep--;
			now=Fa[now];
		}
		if (s[i]=='P') {
			++sum;
			add1(now,sum);
			wh[sum]=now;
			
			val[now]=1;
		}
	}
}
void build(){
	h=t=0; 
	fo(i,0,25) if (ch[0][i]) q[++t]=ch[0][i];
	while (h<t) {
		r=q[++h];
		fo(i,0,25){
			u=ch[r][i];
			if (!u) continue; // 区别
			v=f[r];
			while (v && !ch[v][i]) v=f[v];
			f[u]=ch[v][i];
			q[++t]=u;
		}
	}
}


void Dfs(int x){
	dfn[x]=++zz;
	li[x]=ri[x]=dfn[x];

	for (int i=last[x];i;i=Nex[i]){
		int v=To[i];
		Dfs(v);
		li[x]=min(li[x],li[v]);
		ri[x]=max(ri[x],ri[v]);
	}
}
void dg(int x){
	if (vis[x]) return;
	vis[x]=1;
	update(dfn[x],1);
	
	for (int i=head[x];i;i=nex[i]){
		d[to2[i]]=ask(ri[to1[i]])-ask(li[to1[i]]-1); 
	}
	
	fo(i,0,25) {
		if (ch[x][i]) dg(ch[x][i]);
	}

	update(dfn[x],-1);
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	scanf("%s",s+1);
	work();
	build();

	scanf("%d",&m);
	fo(i,1,m) {
		R(x); R(y);
		add(wh[y],wh[x],i);
	}
	
	fo(i,1,cnt) add2(f[i],i);
	
	Dfs(0);
	dg(0);
	
	fo(i,1,m)  printf("%d\n",d[i]);
	return 0;
}
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

两者其实是有区别的。
前者是找一个字符串，所以可以连这种虚拟边，但是这道题目我的方法需按照trie上dfs进行，如果连上这些边后会导致不能按照正确的顺序访问。
例：

aPaPBbPaPBBBbaPaPBBbPaP
1
1 6