[bzoj3172][Tjoi2013]单词

Description

某人读论文,一篇论文是由许多单词组成.但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次.

Input

第一个一个整数\(N\),表示有多少个单词.

接下来\(N\)行每行一个单词,每个单词由小写字母组成.

Output

输出\(N\)个整数,第\(i\)行的数字表示第\(i\)个单词在文章中出现了多少次.

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

HINT

\(N\;\leq\;200\),单词总长度不超过\(10^6\)

Solution

\(AC\)自动机+\(fail\)树.

\(fail\)树中求子树和即可.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 26
#define K 205
#define N 1000005
using namespace std;
struct trie{
    int chl[M],nxt,cnt;
}t[N];
struct graph{
    int nxt,to;
}e[N];
int a[K],g[N],tot[N],n,m,cnt;
char c[N];
queue q;
inline void addedge(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
} 
inline int insert(int u,int i){
    ++t[u].cnt;
    if(i==m) return u;
    int k=c[i]-'a';
    if(!t[u].chl[k])
        t[u].chl[k]=++cnt;
    return insert(t[u].chl[k],i+1);
}
inline void get_nxt(){
    for(int i=0;i