某人讀論文，一篇論文是由許多單詞組成。但他發現一個單詞會在論文中出現很多次，現在想知道每個單詞分別在論文中出現多少次。
第一個一個整數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++)新聞熱點
疑難解答
