题意
思路
多串匹配,考虑 \(\text{AC}\) 自动机。模拟打字的过程,先建出一棵 \(\text{Trie}\) 树,把它变成自动机。对于每一个询问 \((x,y)\) ,相当于求 \(y\) 在 \(\text{Trie}\) 上的父节点中,有多少个是 \(x\) 在 \(\text{fail}\) 树上的子节点。
不难想到离线,我们对于 \(y\) 记录所有 \(x\) ,求出 \(\text{fail}\) 树上的 \(\text{dfs}\) 序并在 \(\text{Trie}\) 树上 \(\text{dfs}\) ,通过主席树维护遍历到每个点时 \(\text{fail}\) 树 \(\text{dfs}\) 序的信息,每遍历到一个点就把它在 \(\text{fail}\) 树上的 \(\text{dfs}\) 序记进主席树里,并回答在这个点上的所有询问即可。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
#define x first
#define y second
using namespace std;
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+5;
const int NN=N*40;
template<const int maxn,const int maxm>struct Linked_list
{
int head[maxn],to[maxm],nxt[maxm],tot;
Linked_list(){clear();}
void clear(){memset(head,-1,sizeof(head));tot=0;}
void add(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}
#define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])
};
struct ChairmanTree
{
int rt[N],lson[NN],rson[NN],sum[NN];
int tot;
int &operator [](const int x){return rt[x];}
void build()
{
memset(rt,0,sizeof(rt));
sum[tot=0]=lson[0]=rson[0]=0;
}
void create(int &k)
{
sum[++tot]=sum[k],lson[tot]=lson[k],rson[tot]=rson[k];
k=tot;
}
void update(int &k,int x,int val,int l,int r)
{
create(k);
if(l==r){sum[k]+=val;return;}
int mid=(l+r)>>1;
if(x<=mid)update(lson[k],x,val,l,mid);
else update(rson[k],x,val,mid+1,r);
sum[k]=sum[lson[k]]+sum[rson[k]];
}
int query(int k,int L,int R,int l,int r)
{
if(L<=l&&r<=R)return sum[k];
int mid=(l+r)>>1;
if(R<=mid)return query(lson[k],L,R,l,mid);
else if(L>mid)return query(rson[k],L,R,mid+1,r);
else return query(lson[k],L,R,l,mid)+query(rson[k],L,R,mid+1,r);
}
};
Linked_list<N,N>G;
ChairmanTree CT;
int fa[N],son[N][26],ch[N][26],f[N],idx[N];
int L[N],R[N],ord;
int rt,tot;
string str;
int n,m;
vector<pii>vec[N];
int Output[N];
void build(){rt=tot=0;}
void create(int &k)
{
if(!k)
{
k=++tot;
FOR(i,0,25)son[k][i]=ch[k][i]=0;
}
}
void get_fail()
{
queue<int>Q;
while(!Q.empty())Q.pop();
f[rt]=rt;
FOR(i,0,25)
{
if(ch[rt][i])f[ch[rt][i]]=rt,Q.push(ch[rt][i]);
else ch[rt][i]=rt;
}
while(!Q.empty())
{
int u=Q.front();Q.pop();
FOR(i,0,25)
{
if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],Q.push(ch[u][i]);
else ch[u][i]=ch[f[u]][i];
}
}
}
void dfs_fail(int u)
{
L[u]=++ord;
EOR(i,G,u)dfs_fail(G.to[i]);
R[u]=ord;
}
void init(string &str)
{
create(rt);
fa[rt]=rt;
int now=rt;
FOR(i,0,str.length()-1)
{
char a=str[i];
if(a>='a'&&a<='z')
{
if(!ch[now][a-'a'])
{
create(ch[now][a-'a']);
son[now][a-'a']=ch[now][a-'a'];
fa[son[now][a-'a']]=now;
}
now=ch[now][a-'a'];
}
else if(a=='P')
{
n++;
idx[n]=now;
}
else if(a=='B')now=fa[now];
}
}
void dfs_trie(int u)
{
CT.update(CT[u],L[u],1,1,tot);
FOR(i,0,(int)vec[u].size()-1)
{
int x=vec[u][i].x,id=vec[u][i].y;
Output[id]=CT.query(CT[u],L[x],R[x],1,tot);
}
FOR(i,0,25)if(son[u][i])
{
CT[son[u][i]]=CT[u];
dfs_trie(son[u][i]);
}
}
int main()
{
cin>>str>>m;
init(str);
FOR(i,1,m)
{
int x,y;
scanf("%d%d",&x,&y);
vec[idx[y]].push_back(pii(idx[x],i));
}
get_fail();
FOR(i,1,tot)if(f[i]!=i)G.add(f[i],i);
ord=0;dfs_fail(rt);
CT.build();
dfs_trie(rt);
FOR(i,1,m)printf("%d\n",Output[i]);
return 0;
}