【bzoj3172】单词

  • AC自动机重修系列第二题

做过bzoj2434之后，这题就觉得很水了

直接跑AC自动机，统计次数就行了

注意最后要按照拓扑序更新后缀节点，因为当前串中出现过的字符后缀节点所代表的串一定出现过

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000010
using namespace std;
int T,cnt,pos[MAXN],v[MAXN],fail[MAXN],q[MAXN],tr[MAXN][27];
char ch[MAXN];
void extend(int &now){
	int n=strlen(ch+1);
	for(int i=1;i<=n;++i){
		if(!tr[now][ch[i]-'a'])  tr[now][ch[i]-'a']=++cnt;
		now=tr[now][ch[i]-'a'];  v[now]++;
	}
}
void build(){
	int head=0,tail=0;
	for(int i=0;i<26;++i) if(tr[0][i]) q[++tail]=tr[0][i];
	while(++head<=tail){
		int x=q[head];
		for(int i=0;i<26;++i){
			if(!tr[x][i])  tr[x][i]=tr[fail[x]][i];
			else fail[tr[x][i]]=tr[fail[x]][i],q[++tail]=tr[x][i];
		}
	}
	for(int i=tail;i;--i)  v[fail[q[i]]]+=v[q[i]];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;++i)  scanf("%s",ch+1),extend(pos[i]);
	build();
	for(int i=1;i<=T;++i)  printf("%d\n",v[pos[i]]);
	return 0;
}

本文标题:【bzoj3172】单词

文章作者:chty

发布时间:2017年03月07日 - 21时55分

最后更新:2018年03月02日 - 17时24分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,