[BZOJ]单词

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #define M 2000000
 6 using namespace std;
 7 struct point{
 8     int next,to;
 9 }e[M<<1];
10 int n,m,num,cnt;
11 int head[M],fail[M],sum[M],ans[M],end[M];
12 int ch[M][26];
13 char s[M];
14 void add(int from,int to)
15 {
16     e[++num].next=head[from];
17     e[num].to=to;
18     head[from]=num;
19 }
20 void insert(string s,int id)
21 {
22     int len=s.length();
23     int now=0;
24     for(int i=0;i<len;i++)
25     {
26         if(!ch[now][s[i]-‘a‘]) ch[now][s[i]-‘a‘]=++cnt;
27         now=ch[now][s[i]-‘a‘];
28         sum[now]++;
29     }
30     end[id]=now;
31 }
32 void build_fail()
33 {
34     queue<int>q;
35     for(int i=0;i<26;i++)
36         if(ch[0][i])
37         {
38             q.push(ch[0][i]);
39             add(0,ch[0][i]);
40         }
41     while(!q.empty())
42     {
43         int u=q.front(); q.pop();
44         for(int i=0;i<26;i++)
45         {
46             if(ch[u][i])
47             {
48                 fail[ch[u][i]]=ch[fail[u]][i];
49                 q.push(ch[u][i]);
50                 add(ch[fail[u]][i],ch[u][i]);
51             }
52             else ch[u][i]=ch[fail[u]][i];
53         }
54     }
55 }
56 void dfs(int x)
57 {
58     for(int i=head[x];i;i=e[i].next)
59     {
60         int to=e[i].to;
61         dfs(to);
62         sum[x]+=sum[to];
63     }
64 }
65 int main()
66 {
67     scanf("%d",&n);
68     for(int i=1;i<=n;i++)
69     {
70         scanf("%s",s);
71         insert(s,i);
72     }
73     build_fail();
74     dfs(0);;
75     for(int i=1;i<=n;i++) printf("%d\n",sum[end[i]]);
76     return 0;
77 }