[BZOJ2434][Noi2011]阿狸的打字机 AC自动机 fail树 DFS序 离线 树状数组


原题链接
给出一堆串,每次询问第x个串在第y个串中出现多少次.
首先,由于是多个串的匹配问题,我们先建好AC自动机和fail树.
有一个性质,叫作"子串是前缀的后缀",那么"x在y种出现多少次"就等价于"y的前缀中有多少以x为后缀",体现在AC自动机上就是"trie树上root到y之间的点,有多少在fail树上x的子树中".
经典问题吧XwX
将y按照trie树上的dfs序排序,序列中入栈为正出栈为负,将经过的点在fail树上的dfs序扔进树状数组,查询树状数组中某一段的和.完了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 102333
using namespace std;
char s[N];
int m,ch[N][26],fail[N],fa[N],tot=1,node[N],cnt;
int a[N<<1],id1[N],id2[N],size[N],tim1,tim2;//a:AC自动机dfs入栈出栈序列 id1[x]:x的AC自动机入栈编号 id2[x]:x的faill树入栈编号
int sum[N];
inline void fix(int x,int val)
{
    while(x<=tot)sum[x]+=val,x+=x&(-x);
}
inline int qzh(int x)
{
    int re=0;
    while(x)re+=sum[x],x-=x&(-x);
    return re;
}
inline int getsum(int l,int r)
{
    return qzh(r)-qzh(l-1);
}
int head[N],to[N],nxt[N],ecnt;
inline void add(int x,int y)
{
    to[++ecnt]=y;
    nxt[ecnt]=head[x];
    head[x]=ecnt;
}
inline int num(char c)
{
    if(c=='P')return -1;
    if(c=='B')return -2;
    return c-'a';
}
void build_trie()
{
    int len=strlen(s),x=1,i,t;
    for(i=0;i<len;++i)
    {
        t=num(s[i]);
        if(t==-1)node[++cnt]=x;
        else if(t==-2)x=fa[x];
        else
        {
            if(!ch[x][t])ch[x][t]=++tot,fa[ch[x][t]]=x;
            x=ch[x][t];
        }
    }
}
int q[N],l=1,r;
void build_fail()
{
    int x,i;
    for(i=0;i<26;++i)
    {
        if(!ch[1][i])ch[1][i]=1;
        else fail[ch[1][i]]=1,add(1,ch[1][i]),q[++r]=ch[1][i];
    }
    while(l<=r)
    {
        x=q[l++];
        for(i=0;i<26;++i)
        {
            if(!ch[x][i])ch[x][i]=ch[fail[x]][i];
            else fail[ch[x][i]]=ch[fail[x]][i],add(fail[ch[x][i]],ch[x][i]),q[++r]=ch[x][i];
        }
    }
}
void getid1(int x)
{
    id1[x]=++tim1,a[tim1]=x;
    for(int i=0;i<26;++i)if(fa[ch[x][i]]==x)getid1(ch[x][i]);
    a[++tim1]=-x;
}
void getid2(int x)
{
    id2[x]=++tim2,size[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        getid2(to[i]);
        size[x]+=size[to[i]];
    }
}
struct Q
{
    int x,y,id;//存的是原题中的node[x]和node[y]
}qry[N];
inline bool operator<(Q x,Q y)
{
    return id1[x.y]<id1[y.y];
}
int ans[N];
int main()
{
    scanf("%s",s);
    build_trie();
    build_fail();
    getid1(1);
    getid2(1);
    cin>>m;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&qry[i].x,&qry[i].y);
        qry[i].x=node[qry[i].x],qry[i].y=node[qry[i].y];
        qry[i].id=i;
    }
    sort(qry+1,qry+m+1);
    for(int flag,t,now=0,i=1;i<=m;++i)
    {
        while(now<id1[qry[i].y])
        {
            now++;
            flag=(a[now]>0?1:-1),t=a[now]*flag;
            fix(id2[t],flag);
        }
        ans[qry[i].id]=getsum(id2[qry[i].x],id2[qry[i].x]+size[qry[i].x]-1);
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注