某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
3
a
aa
aaa
6
3
1
给出n个单词，求每个单词在这n个单词中各出现了多少次。
不难想到将这n个单词建立一个AC自动机，并在每个节点维护一个sum值，然后将每个单词的每个节点沿着fail指针走一遍，路径上所有sum++。但是这样做会TLE。 考虑到将fail指针反向的话是一棵树，而每个单词的出现次数就是它的单词结尾节点所在的子树中的sum总和。所以先在插入每个单词的时候将路径上所有节点的sum++，然后按照bfs序的反序（即队列从队尾到队首），将每个节点的fail值累加到他的父亲节点（fail指针指向的节点），最后直接输出答案即可。
#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;const int max_size = 1000000 + 10, ch_size = 26;char s[max_size];int n;struct Trie{ int ch[max_size][ch_size]; int f[max_size], sum[max_size], fin[210]; int q[max_size]; int idx['z'+1]; int sz; Trie() {sz = 1; for(char i = 'a'; i <= 'z'; i++) idx[i] = i-'a';} void insert(char *s, int k){ int u = 0, len = strlen(s); for(int i = 0; i < len; i++){ int x = idx[s[i]]; if(!ch[u][x]) ch[u][x] = sz++; u = ch[u][x]; sum[u]++; } fin[k] = u; } void get_fail(){ int lt = 1, rt = 0; for(int i = 0; i < ch_size; i++){ int u = ch[0][i]; if(u){ f[u] = 0; q[++rt] = u; } } while(lt <= rt){ int r = q[lt]; lt++; for(int i = 0; i < ch_size; i++){ int &u = ch[r][i]; if(!u) continue; int v = f[r]; while(v && !ch[v][i]) v = f[v]; f[u] = ch[v][i]; q[++rt] = u; } } for(; rt; rt--) sum[f[q[rt]]] += sum[q[rt]]; }}ac;void init(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%s", s); ac.insert(s, i); }}void work(){ ac.get_fail(); for(int i = 1; i <= n; i++) PRintf("%d/n", ac.sum[ac.fin[i]]);}int main(){ init(); work(); return 0;}新闻热点
疑难解答
