BZOJ3172 [Tjoi2013]单词

 1 /**************************************************************
 2     Problem: 3172
 3     User: rausen
 4     Language: C++
 5     Result: Accepted
 6     Time:308 ms
 7     Memory:117996 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <cstring>
12  
13 using namespace std;
14 const int N = 205;
15 const int Len = 1000005;
16  
17 struct node {
18     int cnt, f;
19     int son[26];
20     bool is_tail;
21 } t[Len];
22  
23 int n, cnt = 1, root = 1;
24 int q[Len], w[N];
25 int head, tail;
26  
27 #define x (int) ch - ‘a‘
28 #define is_alpha(ch) ‘a‘ <= ch && ch <= ‘z‘
29 void build_trie() {
30     int i, j, now, len;
31     char ch;
32     scanf("%d\n", &n);
33     for (i = 1; i <= n; ++i) {
34         now = root;
35         for (j = 1, ch = getchar(); is_alpha(ch); ++j, ch = getchar()) {
36             if (!t[now].son[x])
37                 t[now].son[x] = ++cnt;
38             ++t[now = t[now].son[x]].cnt;
39         }
40         w[i] = now;
41     }
42 }
43  
44 #define Son_p t[p].son[i]
45 #define Son_to t[to].son[i]
46 void build_AC() {
47     int i, to, p;
48     t[root].f = root, q[1] = root;
49     for (head = 0, tail = 1; head < tail; ) {
50         to = t[p = q[++head]].f;
51         for (i = 0; i < 26; ++i) if (Son_p) {
52             q[++tail] = Son_p;
53             t[Son_p].f = Son_to && Son_to != Son_p ? Son_to : root;
54         } else Son_p = t[t[p].f].son[i];
55     }
56 }
57  
58 void work() {
59     int i;
60     for (i = tail; i; --i)
61         t[t[q[i]].f].cnt += t[q[i]].cnt;
62     for (i = 1; i <= n; ++i)
63         printf("%d\n", t[w[i]].cnt);
64 }
65  
66 int main() {
67     build_trie();
68     build_AC();
69     work();
70     return 0;
71 }