codeforces1207G Indie Album AC自动机-DFS-树状数组 算法日常[32/100]

发表于 更新于 分类于 阅读次数：
codeforces1207G Indie Album AC自动机-DFS-树状数组 给要题目中要查询的字符集建立AC自动机 通过dfs求出AC自动机的各节点的及其子节点的size大小,用于后面树状数组确定好匹配的区间 最后再通过DFS让我们要匹配的串去AC自动机上进行跑动,通过树状数组来计数 人生最美好的，就是在你停止生存时，也还能以你所创造的一切为人们服务。

题目链接

codeforces1207G Indie Album

题解

官方题解

  • 看到这里是多个字符串的匹配,我们可以用AC自动机(虽然我一开始想到是用很多后缀自动机(SAM),也有大佬实现了,在官方题解的评论区有),给要题目中要查询的字符集建立AC自动机
  • 并通过trie保持题目让我们构建的串
  • 通过dfs求出AC自动机的各节点的及其子节点的size大小,用于后面树状数组确定好匹配的区间
  • 最后再通过DFS让我们要匹配的串去AC自动机上进行跑动,通过树状数组来计数(菜鸡我第一次见这种sao操作)
  • 对于每个匹配完的DFS都要清除掉树状数组上的记录,以免对其他部分造成影响

AC代码

好像比赛时只有30个大佬过了这题,所以代码不是我这个小菜鸡写的,是借鉴了ASDFZ的一个oi大佬(我猜他是搞oi的)的代码

以及附上我对他代码的理解注释,我觉得这份代码写得真牛逼

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
// 59470538	Aug/25/2019 23:34UTC+8	LittleBeetle	G - Indie Album	GNU C++11	Accepted	561 ms	89100 KB
// By LittleBeetle, contest: Educational Codeforces Round 71 (Rated for Div. 2), problem: (G) Indie Album, Accepted, #
#include<cstdio>
#include<vector>
using namespace std;
const int N=400002;
int n,q,i,j,k,opt,h[N],tt[N],v[N],ans[N];
char ch[3],s[N],ti[N];
vector<int>p[N],id[N];
void add(int a,int b){
	// 看AC.dfs()发现,h[a]记录的应该是最后一个a指向的节点,而tt则记录的是同一层节点的前向路径,所以不是什么trie,而是一个奇特的最右儿子兄弟树!
	// 因此可以AC.dfs()可以通过使用这样的for循环 `for(int j=H[i];j;j=to[j])` 访问整个一层的节点
	tt[++k]=h[a];
	h[a]=k;
	// 这里v[k] 就是记录的是id节点的value, 用int 记录 char 是没有关系的
	v[k]=b;
}
struct AC{
	int cnt,t[N][26],fail[N],q[N],l,r,i,j,k;
	int H[N],to[N],V[N],dfn[N],sz[N],Tim,c[N],loc[N];
	int insert(char *s){
		for(i=j=1;s[j];j++){
			if(!t[i][s[j]-97])
				t[i][s[j]-97]=++cnt;
			i=t[i][s[j]-97];
		}
		return i;
	}
	void add(int a,int b){
		to[++k]=H[a];
		H[a]=k;
		V[k]=b;
	}
	// 深度遍历右儿子以及右儿子的兄弟,统计size的值
	void dfs(int i){
		// dfn 是 各个节点被深度遍历的顺序的hash记录
		dfn[i]=++Tim;
		sz[i]=1;
		for(int j=H[i];j;j=to[j])
			dfs(V[j]),sz[i]+=sz[V[j]];
	}
	void Build(){
		// bfs的l,r的写法
		// 根节点用的是1
		l=0;r=-1;
		for(j=0;j<26;j++)
			if(t[1][j])
				fail[t[1][j]]=1,add(1,t[1][j]),q[++r]=t[1][j];
			else
				t[1][j]=1;
		while(l<=r){
			i=q[l++];
			for(j=0;j<26;j++)
				if(t[i][j])
					fail[t[i][j]]=t[fail[i]][j],add(fail[t[i][j]],t[i][j]),q[++r]=t[i][j];
				else
					t[i][j]=t[fail[i]][j];
		}
		dfs(1);
	}
	// 这是一个反向树状数组,所以序数小的节点是大节点(父节点)
	void Add(int x,int y){
		while(x)
			c[x]+=y,x-=x&-x;
	}
	int Query(int x){
		int s=0;
		while(x<=cnt)
			s+=c[x],x+=x&-x;
		return s;
	}
	void DFS(int i){
		Add(dfn[loc[i]],1);
		// 测试发现,i=0等一些没有到过的值的时候,是不会进入for的...
		for(int j=0;j<p[i].size();j++)
			ans[id[i][j]]=Query(dfn[p[i][j]])-Query(dfn[p[i][j]]+sz[p[i][j]]);
		// 卡很久一个点,注意这里的for循环也是右儿子及其兄弟的遍历方式...===> 而且这里是要查询自动机的初始串的遍历!!!!!
		for(int j=h[i];j;j=tt[j]){
			// 这里是跑AC自动机的核心,失配之后 从i跑向j,然后再DFS
			// 对的,跑自动机的时候是不用fail的,然后在这里跑下去,所以先算好了下面的,然后回溯算好了上面的
			// 每一小块都要把对应的树状数组部分清除掉

			// 2019年10月08日21:21:13 突然那么一瞬间,总算想清楚了多一点点
			// 比如你dadada,然后AC自动机上只有模式串da,所以你虽然dfs向下走dadada,但是你每次添加的位置都是loc[v[i]],所以这里是一个比较松的耦合!
			loc[v[j]]=t[loc[i]][s[v[j]]-97];
			DFS(v[j]);
		}
		Add(dfn[loc[i]],-1);
	}
	void work(){
		loc[0]=1;
		DFS(0);
	}
}T;
void init(){
	T.cnt=1;
	scanf("%d",&n);
	for(i=1;i<=n;i++,j=0){
		scanf("%d",&opt);
		if(opt==2)
			scanf("%d",&j);
		add(j,i);
		scanf("%s",ch);
		s[i]=*ch;
	}
	scanf("%d",&q);
	for(i=1;i<=q;i++){
		scanf("%d%s",&j,ti+1);
		p[j].push_back(T.insert(ti));
		id[j].push_back(i);
	}
}
int main(){
	init();
	T.Build();
	T.work();
	for(i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}

背后故事

菜鸡我前前后后理解了这个题目3天…没想到自己被自己不太认识的树状数组卡了好久(丢人了…)–> 继续加油吧

每天一句叨叨

人生最美好的，就是在你停止生存时，也还能以你所创造的一切为人们服务。