[NOI2011] 阿狸的打字机

Description

给定(N(Nleq 10^5))个串，(m(mleq 10^5))次询问，每次询问第(x)个串在第(y)个串中出现了几次。

Solution

脑抽又调了一个小时。。。

考虑AC自动机fail指针的含义，如果 (fail[x]=y) 那说明以 (y) 结尾的串在 (x) 中出现了。

于是询问 (x) 在 (y) 中出现了几次实际上就是问trie树上根到 (y) 的路径有多少点的 (fail) 指针直接或间接指向了 (x) 的结尾节点。可以把 (fail) 指针当做树边拎出来建树。

于是询问变成在新的 (fail) 树上以点 (x) 为根的子树中有多少点是在trie树上根到 (y) 的路径上的。

先dfs一遍 (fail) 树求出dfs序转化为序列上的问题。

直接在 (fail) 树上做貌似不是很好做，我们回到原来的trie树上，dfs 一遍整个trie树。进入一个点就在序列上对应位置+1，退出一个点就在对应位置-1，这样保证了只有当前路径是有值的。如果碰到了单词节点，就相当于我们遇到了询问 ((x,y)) 中的 (y)，扫一下所有的 (x)，查子树和就行了。

Code

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::min;
using std::max;
using std::swap;
using std::vector;
const int M=8e5+5;
const int N=1e5+5;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)

vector< pii > v[N];
vector<int> js[M];char a[N];
int tot,head[M],ch[M][27],ans[N],fa[M];
int n,m,cnt,fs[N],fail[M],dfn[M],f[M],sze[M];

struct Edge{
    int to,nxt;
}edge[M];

void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}

void add(int x){
    while(x) f[x]++,x-=x&-x;
}

void clr(int x){
    while(x) f[x]--,x-=x&-x;
}

int query(int x){
    int now=0;
    while(x<=tot) now+=f[x],x+=x&-x;
    return now;
}

int getint(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=X*10+ch-48,ch=getchar();
    if(w) return -X;return X;
}

void getfail(){
    std::queue<int> q;
    for(int i=0;i<26;i++)
        if(ch[0][i])
            q.push(ch[0][i]);
    while(q.size()){
        int u=q.front();q.pop();add(fail[u],u);
        for(int i=0;i<26;i++){
            if(ch[u][i]) 
                fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
            else ch[u][i]=ch[fail[u]][i];
        }
    }
}

void dfs(int now){
    sze[now]=1;dfn[now]=++tot;
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        dfs(to);sze[now]+=sze[to];
    } 
}

void sdfs(int now){
    add(dfn[now]);
    for(int x:js[now])
        for(auto y:v[x])
            ans[y.second]=query(dfn[fs[y.first]])-query(dfn[fs[y.first]]+sze[fs[y.first]]);
    for(int i=0;i<26;i++)
        if(ch[now][i])
            sdfs(ch[now][i]);
    clr(dfn[now]);
}

signed main(){
    scanf("%s",a+1);
    int len=strlen(a+1),now=0;
    for(int i=1;i<=len;i++){
        if(a[i]>='a' and a[i]<='z'){
            if(!ch[now][a[i]-'a']) ch[now][a[i]-'a']=++tot,fa[tot]=now;
            now=ch[now][a[i]-'a'];
        }
        else if(a[i]=='B')
            now=fa[now];
        else n++,js[now].pb(n),fs[n]=now;
    } tot=0;getfail();dfs(0);int cnts=0;
    memset(ch,0,sizeof ch);now=0;
    for(int i=1;i<=len;i++){
        if(a[i]>='a' and a[i]<='z'){
            if(!ch[now][a[i]-'a']) ch[now][a[i]-'a']=++cnts;
            now=ch[now][a[i]-'a'];
        }
        else if(a[i]=='B')
            now=fa[now];
    }
    m=getint();
    for(int i=1;i<=m;i++){
        int x=getint(),y=getint();
        v[y].pb(mp(x,i));
    } sdfs(0);
    for(int i=1;i<=m;i++)
        printf("%d
",ans[i]);
    return 0;
}