Trie树、AC自动机模板

定义：

int trie[sigma(len)][26],num;//注意，点是[0,25]
int fail[sigma(len)];//该节点的后缀节点编号
bool danger[sigma(len)];//该节点是否有字符串匹配结束

建Trie树：

void add(int x,int p) {
	if (p>len) {
		danger[x]=true;
		return;
	}
	int tmp=str[p]-'a';
	if (trie[x][tmp]==-1) trie[x][tmp]=++num;
	add(trie[x][tmp],p+1);
}

或者

void add() {
	int nowp=0;
	for (int i=1;i<=len;i++) {
		int tmp=str[i]-'a';
		if (tree[nowp][tmp]==-1) tree[nowp][tmp]=++num;
		nowp=tree[nowp][tmp];
	}
	danger[nowp]=true；
}

建Trie图：

void build_ac() {
	fail[0]=0;//关于root需要特殊处理
	for (int i=0;i<26;i++) {
		int v=trie[0][i];
		if (v!=-1) {
			fail[v]=root;
			que.push(v);
		} else trie[0][i]=0;
	}
	while (!que.empty()) {//bfs序保证所有深度较浅的节点已经完成
		int u=que.front();
		que.pop();
		for (int i=0;i<26;i++) {
			int v=trie[u][i];
			if (v==-1) {
				trie[u][i]=trie[fail[u]][i];//儿子的等效节点，是该点的后缀节点的儿子
				continue;
			}
			fail[v]=trie[fail[u]][i];//儿子的后缀，是该点的后缀节点的儿子
			que.push(v);
			danger[v]=danger[v]|danger[fail[v]];//如果其后缀节点也是危险节点，那么它也是危险节点
		}
	}
}