p3966单词

后缀自动机版本：

所有的串用(char)('z'+1)连起来，然后建自动机。再用原串在自动机上跑。跑到的位置的endpos就是出现的次数。不过内存有点大。

#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=*SZ,APB=,one=,INF=0x7FFFFFFF,mod=;

int n,len,cnt,slink[SSZ],nex[SSZ][APB],maxlen[SSZ];

int minlen[SSZ],endpos[SSZ],in[SSZ];

char ch[SZ];

string str[SZ];

bool green[SSZ];

void add(string &x)

{

    for(int i=;i<x.size();++i)

    {

        ch[++len]=x[i];

    }

    ch[++len]='z'+;

}

int ins(int pre,int c)

{

    int z=++cnt,u=pre;

    green[z]=;

    for(;u!=-&&!nex[u][c];u=slink[u])nex[u][c]=z;

    maxlen[z]=maxlen[pre]+;

    if(u==-)

    {

        slink[z]=;

    }

    else

    {

        int x=nex[u][c];

        if(maxlen[x]==maxlen[u]+)

        {

            slink[z]=x;

        }

        else

        {

            int v=++cnt;

            memcpy(nex[v],nex[x],sizeof(nex[x]));

            maxlen[v]=maxlen[u]+;

            slink[v]=slink[x];

            minlen[v]=maxlen[slink[v]]+;

            slink[x]=slink[z]=v;

            minlen[x]=maxlen[v]+;

            for(;u!=-&&nex[u][c]==x;u=slink[u])

            nex[u][c]=v;

        }

    }

    minlen[z]=maxlen[slink[z]]+;

    return z;

}

void topo()

{

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

    {

        ++in[slink[i]];

    }

    stack<int> stk;

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

    {

        if(!in[i])stk.push(i),endpos[i]=;

    }

    for(;stk.size();)

    {

        int top=stk.top();

        stk.pop();

        int pre=slink[top];

        endpos[pre]+=endpos[top],--in[pre];

        if(!in[pre]&&pre)

        {

            if(green[pre])++endpos[pre];

            stk.push(pre);

        }

    }

}

void init()

{

    cin>>n;

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

    {

        cin>>str[i];

        add(str[i]);

    }

    int pre=;

    slink[]=-;

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

    {

        pre=ins(pre,ch[i]-'a');

    }

    topo();

}

int calc(string &x)

{

    int cur=;

    for(int i=;i<x.size();++i)

    {

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

        cur=nex[cur][c];

    }

    return endpos[cur];

}

void work()

{

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

    {

        cout<<calc(str[i])<<endl;

    }

}

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 ;

}