hsy单词

题意：略

在ac自动机上，一个节点出现的次数等于能通过fail到它的节点的次数之和。而叶节点就等于它被爬过的次数。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,SSZ=,APB=,one=,INF=0x7FFFFFFF,mod=;

int n,nex[SZ][APB],cnt,num[SZ];

int fail[SZ],match[SZ],in[SZ],ans[SZ];

char ch[SZ];

void build(int x)

{

    int cur=;

    for(int i=;ch[i];++i)

    {

        int c=ch[i]-'a';

        if(!nex[cur][c])nex[cur][c]=++cnt;

        cur=nex[cur][c];

        ++num[cur];

        //cout<<num[cur]<<endl;

    }

    match[x]=cur;

}

void build_fail()

{

    queue<int> q;

    q.push();

    for(;q.size();)

    {

        int fr=q.front();

        q.pop();

        for(int i=;i<APB;++i)

        {

            if(nex[fr][i])

            {

                int u=nex[fr][i];

                if(fr==)

                {

                    fail[u]=;

                }

                else

                {

                    int v=fail[fr];

                    for(;!nex[v][i]&&v;v=fail[v]);

                    if(nex[v][i])fail[u]=nex[v][i];

                    else fail[u]=;

                }

                q.push(u);

            }

        }

    }

}

void topo()

{

    for(int i=;i<=cnt;++i)

    {

        ++in[fail[i]];

    }

    stack<int> stk;

    for(int i=;i<=cnt;++i)

    {

        if(!in[i])

        {

            stk.push(i);

            //cout<<"i: "<<i<<endl;

        }

        ans[i]=num[i];

    }

    for(;stk.size();)

    {

        int top=stk.top();

        stk.pop();

        --in[fail[top]],ans[fail[top]]+=ans[top];

        if(!in[fail[top]])

        {

            stk.push(fail[top]);

        }

    }

}

void init()

{

    cin>>n;

    for(int i=;i<=n;++i)

    {

        cin>>ch+;

        build(i);

    }

    build_fail();

    topo();

    for(int i=;i<=n;++i)

    {

        cout<<ans[match[i]]<<endl;

    }

}

void work()

{

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    //cin>>casenum;

    //cout<<casenum<<endl;

    //for(int time=1;time<=casenum;++time)

    //for(int time=1;cin>>n>>qnum,n;++time)

    {

        //cout<<"Case "<<time<<": ";

        init();

        work();

    }

    return ;

}