[BZOJ3881][Coci2015]Divljak fail树+树链的并


原题链接
给出字符串集合s,你有一个空字符串集合t,两种操作:
1.向t中塞一个串
2.查询t中有多少串包含s_x
容易想到对s建立AC自动机,每次将新串扔进去跑,将新串所有经过的点到fail树树根的路径上的点答案+1,每次直接查询答案.
然而这样做会重复,怎么办呢?
注意到重复多少次都只算一次,我们可以使用树链的并.方法就是将所有点按照dfs序排序,加入所有点再减掉所有相邻点的lca.
注意到每次查询子树,并且是单点更新,可以使用树状数组.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2002333
using namespace std;
int n,m;
char s1[N];
int ch[N][26],fa[N][23],Log[N],tot=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;
}
int node[N];
inline int insert(char *str)
{
    int len=strlen(str),x=1,i;
    for(i=0;i<len;++i)
    {
        if(!ch[x][str[i]-'a'])ch[x][str[i]-'a']=++tot;
        x=ch[x][str[i]-'a'];
    }
    return x;
}
inline void add_fail(int x,int fail)
{
    fa[x][0]=fail;
    add(fail,x);
}
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 add_fail(ch[1][i],1),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[fa[x][0]][i];
            else add_fail(ch[x][i],ch[fa[x][0]][i]),q[++r]=ch[x][i];
        }
    }
}
int id[N],deep[N],size[N],tim;
void getid(int x)
{
    id[x]=++tim,deep[x]=deep[fa[x][0]]+1,size[x]=1;
    for(int i=head[x];i;i=nxt[i])getid(to[i]),size[x]+=size[to[i]];
}
int sum[N];
inline void fix(int x,int val)
{
    while(x<=tot)sum[x]+=val,x+=x&(-x);
}
inline int S(int x)
{
    int re=0;
    while(x)re+=sum[x],x-=x&(-x);
    return re;
}
inline int getsum(int l,int r)
{
    return S(r)-S(l-1);
}
int z[N],top;
inline bool cmp(int x,int y)
{
    return id[x]<id[y];
}
void lca_pre()
{
    int i,x;
    for(i=2;i<=tot;++i)Log[i]=Log[i>>1]+1;
    for(i=1;i<=Log[tot];++i)
        for(x=1;x<=tot;++x)fa[x][i]=fa[fa[x][i-1]][i-1];
}
inline int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int i;
    for(i=Log[deep[x]];i+1;--i)if(deep[fa[x][i]]>=deep[y])x=fa[x][i];
    if(x==y)return x;
    for(i=Log[deep[x]];i+1;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
inline void drive(char *str)
{
    int len=strlen(str),x=1,i;
    top=0;
    for(i=0;i<len;++i)
    {
        x=ch[x][str[i]-'a'];
        z[++top]=x;
    }
    sort(z+1,z+top+1,cmp);
    for(i=1;i<=top;++i)fix(id[z[i]],1);
    for(i=2;i<=top;++i)fix(id[lca(z[i],z[i-1])],-1);
}
inline int getans(int x)
{
    return getsum(id[x],id[x]+size[x]-1);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s1);
        node[i]=insert(s1);
    }
    build_fail();
    getid(1);
    lca_pre();
    cin>>m;
    for(int flag,x,i=1;i<=m;++i)
    {
        scanf("%d",&flag);
        if(flag==1)
        {
            scanf("%s",s1);
            drive(s1);
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",getans(node[x]));
        }
    }
    return 0;
}

发表评论

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