zcmimi's blog
查看原题

点击跳转

首先根据输入的字符串构造trie

然后构建AC自动机

利用了fail树的一个性质:

y节点的fail指针指向x节点,那么 根到x形成的字符串 一定在 根到y形成的字符串 中出现过

那么我们对于每个询问x y,只需要找出根到y上的节点有多少个fail指针直接或间接指向x的,就是答案

构建fail树之后使用dfs序+树状数组统计

#include<bits/stdc++.h>
#define gc getchar()
#define fur(i,x,y) for(int i=x;i<=y;++i)
void cmin(int &x,int y){if(x>y)x=y;}void cmax(int &x,int y){if(x<y)x=y;}
void in(int &x){x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);if(f)x=-x;}
const int N=100011;
using std::list,std::pair;
char ch[N];
int n,m,sz,tot,cnt,c[N][26],fa[N],fail[N],p[N],q[N],head[N],ans[N];
list<int>e[N];
list<pair<int,int>>que[N];
int L[N],R[N],dfn,s[N];
void dfs(int x){
    L[x]=++dfn;
    for(int to:e[x])dfs(to);
    R[x]=dfn;
}
void add(int x,int v){for(;x<=sz;x+=x&-x)s[x]+=v;}
int ask(int x){int res=0;for(;x;x-=x&-x)res+=s[x];return res;}
int main(){
    scanf("%s",ch),n=strlen(ch);
    int x=1,y,h=0,t=1;
    sz=1;fur(i,0,25)c[0][i]=1;
    fur(i,0,n-1)
        if(ch[i]=='P')p[++tot]=x;
        else if(ch[i]=='B')x=fa[x];
        else{
            if(!c[x][ch[i]-'a'])fa[c[x][ch[i]-'a']=++sz]=x;
            x=c[x][ch[i]-'a'];
        }
    q[0]=1,fail[1]=0;
    while(h<t){
        x=q[h++];
        fur(i,0,25)
            if(c[x][i])fail[c[x][i]]=c[fail[x]][i],q[t++]=c[x][i];
            else c[x][i]=c[fail[x]][i];
    }
    fur(i,1,sz)e[fail[i]].push_back(i);
    in(m);
    fur(i,1,m)in(x),in(y),que[y].push_back(std::make_pair(i,x));
    dfs(1);
    x=1,tot=0;
    fur(i,0,n-1)
        if(ch[i]=='P'){
            ++tot;for(auto x:que[tot])
                ans[x.first]=ask(R[p[x.second]])-ask(L[p[x.second]]-1);
        }
        else if(ch[i]=='B')add(L[x],-1),x=fa[x];
        else x=c[x][ch[i]-'a'],add(L[x],1);
    fur(i,1,m)printf("%d\n",ans[i]);
}
LG 2414 [NOI2011]阿狸的打字机
comment评论
Search
search