3172: [Tjoi2013]单词

Time Limit: 10 Sec  Memory Limit: 512 MB

Submit: 4057  Solved: 1964

[][][]

Description

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

Input

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

Output

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

Sample Input

3

a

aa

aaa

Sample Output

6

3

1

HINT

 

Source

这题把fail指针逆向形成了一个叫fail树的东西  fail树的父亲结点一定是儿子节点的子串！！！

1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=1000006; 5 int n; 6 struct Aho{ 7     struct state{ 8         int next[26]; 9         int cnt,fail;10         state (){11             memset(next,0,sizeof(next));12             cnt=fail=0;13         }14     }sst[MAX];15     16     int q[MAX],low,high,tot,size,end[205],sum[MAX];17     18     void init(){19         int i,j;20         low=1,high=tot=size=0;21         memset(sum,0,sizeof(sum));22     }23     24     void insert(char *s){25         int i,j,ls=strlen(s);26         int now=0;27         for (i=0;i