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 }