2542 单词

2013年省队选拔赛天津市队选拔赛

 时间限制: 2 s

 空间限制: 256000 KB

 题目等级 : 大师 Master

题目描述 Description

小张最近在忙毕业，所以一直在读论文。一篇论文是由许多单词组成的。

但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。

输入描述 Input Description

第一行一个整数N，表示有N个单词，接下来N行,每行一个单词，每个单词都由小写字母组成（N<=200）

输出描述 Output Description

输出N个整数，第i行的数表示第i个单词在文章中出现了多少次。

样例输入 Sample Input

3
a
aa
aaa

样例输出 Sample Output

6

3

1

数据范围及提示 Data Size & Hint

30%的数据 单词总长度不超过10^3
100%的数据 单词总长度不超过10^6

————————————————————————————————————————————————————————————————————————————————

一看是AC自动机是没有问题的，但是建完AC自动机后该如何做呢？

当然可以直接用AC自动机的fail指针向前跳，但是这样要枚举单词内的每个位置，严重超时。

这里要用到一个很有用的工具——fail树。

当AC自动机建完以后，我们发现每一个节点都只有一个失败指针（根节点的可以忽略），且沿着失败指针最终能走到根节点。

这样我们将失败指针反向就可以变成一棵树。

这棵树的有些重要的性质：

1、以x节点为根的子树中每个节点代表的字符串都以x点所代表的字符串为后缀。

2、节点x代表的字符串的最大后缀为父节点代表的字符串。

这样我们在插入字符串是把经过的每个节点的val值都加1，就相当于统计的对应前缀出现的次数。

然后通过dfs将val变为val加它所有子树的val和。也就是以（s）为前缀的字符串个数+以（*+s）为前缀的字符串的个数+以（**+s）为前缀的个数+。。。。。

这样s出现的次数就是s串尾对应的val值。

比较难想，但是fail树真的很有用。

————————————————————————————————————————————————————————————————————————————————

1 #include
2 using namespace std;
3 const int maxn=1e6+3;
4 const int maxs=26;
5 struct edge{
6 int u,v,next;
7 }e[maxn];
8 int head[maxn],js=0;
9 void addage(int u,int v)
10 {
11 e[++js].u=u;e[js].v=v;
12 e[js].next=head[u];head[u]=js;
13 }
14 struct AC{
15 int ch[maxn][maxs];
16 int val[maxn],f[maxn];
17 int sz;
18 AC(){
19 memset(ch[0],0,sizeof(ch[0]));
20 val[0]=0;
21 sz=1;
22 }
23 int idx(char c){
24 return c-'a';
25 }
26 int insert(char *s){
27 int n=strlen(s),cur=0;
28 for(int i=0,c;iq;
42 f[0]=0;
43 for(int c=0;c<maxs;c++){
44 int v=ch[0][c];
45 if(v){
46 f[v]=0;
47 q.push(v);
48 addage(0,v);
49 }
50 }
51 while(!q.empty()){
52 int u=q.front();q.pop();
53 for(int c=0;c<maxs;++c){
54 int v=ch[u][c];
55 if(v){
56 q.push(v);
57 int r=f[u];
58 while(r && !ch[r][c])r=f[r];
59 f[v]=ch[r][c];
60 addage(f[v],v);
61 }
62 }
63 }
64 }
65 }ac;
66 int n;
67 int wz[201];
68 char s[maxn];
69 void dfs(int u,int f)
70 {
71 for(int i=head[u];i;i=e[i].next){
72 int u=e[i].u,v=e[i].v;
73 if(v==f)continue;
74 dfs(v,u);
75 ac.val[u]+=ac.val[v];
76 }
77 }
78 int main()
79 {
80 scanf("%d",&n);
81 for(int i=0;i<n;++i){
82 scanf("%s",s);
83 wz[i]=ac.insert(s);
84 }
85 ac.getfail();
86 dfs(0,-1);
87 for(int i=0;i<n;i++)
88 printf("%d\n",ac.val[wz[i]]);
89 return 0;
90 }