Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a aa aaaSample Output
6
3 1哎，这不是多字符串的问题吗？我们首先就想到了AC自动机！
fail指针的意义是什么呢？就是一个后缀链接，而后缀是覆盖了所有的子串的，所以我们可以用一次树DP，就统计出了每一个单词出现的次数。/************************************************************** Problem: 3172 User: geng4512 Language: C++ Result: Accepted Time:256 ms Memory:237132 kb****************************************************************/#include#define MAXN 2000000#define MAXC 26int a[MAXN][MAXC], pre[MAXN], sz = 1, q[MAXN], cnt[MAXN], ed[MAXN], n;char s[MAXN];inline int Insert(char *s) { int c, p = 1; for(int i = 0; s[i]; ++ i) { c = s[i] - 'a'; if(!a[p][c]) a[p][c] = ++ sz; p = a[p][c]; ++ cnt[p]; } return p;}void Build() { int l = 1, r = 0; for(int i = 0; i < MAXC; ++ i) if(!a[1][i]) a[1][i] = 1; else { pre[a[1][i]] = 1; q[++ r] = a[1][i]; } while(l <= r) { int u = q[l ++]; for(int i = 0; i < MAXC; ++ i) if(!a[u][i]) a[u][i] = a[pre[u]][i]; else { pre[a[u][i]] = a[pre[u]][i]; q[++ r] = a[u][i]; } } for(int i = r; i; -- i) cnt[pre[q[i]]] += cnt[q[i]];}int main() { scanf("%d", &n); for(int i = 1; i <= n; ++ i) { scanf("%s", s); ed[i] = Insert(s); } Build(); for(int i = 1; i <= n; ++ i) printf("%d\n", cnt[ed[i]]); return 0;}