bzoj3172 Ac自动机

根据fail树的性质 我们在建树的时候每建一个串就将他路径上的点全部加1表示这个串的后缀又出现了一次 然后从下到上把sum加起来就可以得到答案了

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int size=,M=;

char c[M];

int w[],n;

struct node{

    int sum,fail[M],a[M][],ans[M];

    int id(char s){return s-'a'+;}

    void insert(char s[],int &x){

        int k=,L=strlen(s);

        for(int i=;i<L;i++){

            int now=id(s[i]);

            if(!a[k][now]) a[k][now]=++sum;

            ans[a[k][now]]++;

            k=a[k][now];

        }

        x=k;

    }

    int q[M],head,tail;

    void Ac_boy(){

        for(int i=;i<=size;i++){

            int now=a[][i];

            if(now) q[tail++]=now;

        }

        while(head!=tail){

            int x=q[head++];

            for(int i=;i<=size;i++){

                int now=a[x][i];

                if(!now){a[x][i]=a[fail[x]][i];continue;}

                q[tail++]=now;

                fail[now]=a[fail[x]][i];

            }

        }

    }

    void work(){

        for(int i=tail-;i>=;i--) ans[fail[q[i]]]+=ans[q[i]];

        for(int i=;i<=n;i++) printf("%d\n",ans[w[i]]);

    }

}node;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%s",c),node.insert(c,w[i]);

    node.Ac_boy(); node.work();

    return ;

}