分析
首先考虑按照题意建出一个AC自动机,
然后(s[x])在(s[y])出现的次数也就是
在fail树上,根节点到(y)中一共出现了多少个(x),
在(x)的终止节点处统计子树中根节点到(y)有多少个
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <vector>
#define rr register
using namespace std;
const int N=100011; vector<int>KU[N];
struct node{int y,next;}e[N];
int endd[N],sit[N],k,X[N],dfn[N],Trie[N][26];
int tot,c[N],n,m,rfn[N],as[N],ans[N];
struct I_AC_THE_TASK{
int Tot,trie[N][26],fail[N],FA[N],now;
inline void Append(char c){
if (!trie[now][c-97]) trie[now][c-97]=++Tot,FA[Tot]=now;
now=trie[now][c-97];
}
inline void Build(){
rr queue<int>q; q.push(1);
while (!q.empty()){
rr int x=q.front(); q.pop();
for (rr int i=0;i<26;++i)
if (!trie[x][i]) trie[x][i]=trie[fail[x]][i];
else fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
}
}
}AC;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline void update(int x,int y){for (;x<=tot;x+=-x&x) c[x]+=y;}
inline signed query(int l,int r){
rr int ans=0; --l;
for (;r>l;r-=-r&r) ans+=c[r];
for (;l>r;l-=-l&l) ans-=c[l];
return ans;
}
inline void add(int x,int y){e[++k]=(node){y,as[x]},as[x]=k;}
inline void dfs1(int x){
dfn[x]=++tot;
for (rr int i=as[x];i;i=e[i].next)
dfs1(e[i].y);
rfn[x]=tot;
}
inline void dfs2(int x){
update(dfn[x],1);
if (endd[x]){
rr int ed=endd[x];
for (rr int i=0;i<KU[ed].size();++i){
rr int RK=KU[ed][i],p=sit[X[RK]];
ans[RK]=query(dfn[p],rfn[p]);
}
}
for (rr int i=0;i<26;++i)
if (Trie[x][i]) dfs2(Trie[x][i]);
update(dfn[x],-1);
}
signed main(){
AC.Tot=AC.now=AC.FA[1]=1; rr char c=getchar();
for (rr int i=0;i<26;++i) AC.trie[0][i]=1;
while (!islower(c)) c=getchar();
while (isalpha(c)){
if (c=='B') AC.now=AC.FA[AC.now];
else if (c=='P') endd[AC.now]=++n,sit[n]=AC.now;
else AC.Append(c);
c=getchar();
}
memcpy(Trie,AC.trie,sizeof(AC.trie));
AC.Build(),m=iut();
for (rr int i=1;i<=m;++i){
rr int x=iut(),y=iut();
KU[y].push_back(i),X[i]=x;
}
for (rr int i=2;i<=AC.Tot;++i) add(AC.fail[i],i);
dfs1(1),dfs2(1);
for (rr int i=1;i<=m;++i) print(ans[i]),putchar(10);
return 0;
}