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

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define N 1000005 7 using namespace std; 8 int pos[N],n; 9 struct acm10 {11     int cnt;12     int next[N][26],q[N],sum[N],fail[N];13     char ch[N];14     acm()15     {16         cnt=1;17         for(int i=0;i<26;i++)next[0][i]=1;18     }19     void insert(int &pos)20     {21         int now=1;22         scanf("%s",ch);23         int len=strlen(ch);24         for(int i=0;i<len;i++)25         {26             if(!next[now][ch[i]-‘a‘])next[now][ch[i]-‘a‘]=++cnt;27             now=next[now][ch[i]-‘a‘];28             sum[now]++;29         }30         pos=now;31     }32     void buildfail()33     {34         int head=0,tail=1;35         q[0]=1;fail[1]=0;36         while(head!=tail)37         {38             int now=q[head++];39             for(int i=0;i<26;i++)40             {41                 int v=next[now][i];42                 if(!v)continue;43                 int k=fail[now];44                 while(!next[k][i])k=fail[k];45                 fail[v]=next[k][i];46                 q[tail++]=v;47             }48         }49         for(int i=tail-1;i>=0;i--)50             sum[fail[q[i]]]+=sum[q[i]];51     }52 }trie;53 int main()54 {55     scanf("%d",&n);56     for(int i=1;i<=n;i++)trie.insert(pos[i]);57     trie.buildfail();58     for(int i=1;i<=n;i++)printf("%d\n",trie.sum[pos[i]]);59 //    system("pause");60     return 0;61 }62