(题目链接)

题意

　　$n$个单词组成文本，问每个单词在文本中出现了几次。

Solution

　　题目数据范围写错了，mdzz。

　　构AC自动机统计每个点被经过的次数，然后按照fail树自底向上更新。

细节

　　？

代码

// bzoj3172#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long long#define inf (1ll<<30)#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=1000010;int n,sz=1,pos[maxn],q[maxn];char s[maxn];struct node { int son[26],next,sum; int& operator [] (int x) {return son[x];}}tr[maxn];namespace ACM { void insert(char *r,int t) { int p=1,len=strlen(r+1); for (int i=1;i<=len;i++) { if (!tr[p][r[i]-'a']) tr[p][r[i]-'a']=++sz; p=tr[p][r[i]-'a']; tr[p].sum++; } pos[t]=p; } void buildfail() { int l=1,r=1;q[1]=1; tr[1].next=0; while (l<=r) { int x=q[l++]; for (int i=0;i<26;i++) if (tr[x][i]) { int k=tr[x].next; while (!tr[k][i]) k=tr[k].next; tr[tr[x][i]].next=tr[k][i]; q[++r]=tr[x][i]; } } for (int i=r;i>=1;i--) tr[tr[q[i]].next].sum+=tr[q[i]].sum; }}using namespace ACM;int main() { scanf("%d",&n); for (int i=0;i<26;i++) tr[0][i]=1; for (int i=1;i<=n;i++) { scanf("%s",s+1); insert(s,i); } buildfail(); for (int i=1;i<=n;i++) printf("%d\n",tr[pos[i]].sum); return 0;}