Luogu

分析

做完这题感觉对 AC 自动机有了新的理解...

注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀（这里建议想一想 fail 的定义），因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。

然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串，于是我们只需要把 $Y$ 的前缀都加上 $1$ ，再查 fail 树上 $X$ 子树的权值和即可。把所有前缀加 $1$ 相当于把 trie 上到根的一条路径加 $1$。

具体的子树权值和用树状数组维护即可。

实现起来有一些细节。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct edge { int v,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int ch[N][26],fail[N],fa[N],pos[N],tot=0,stot=0;
inline void insert(char* s,int l) { int now=0;
    for (re int i=1;i<=l;++i) {
        if (s[i]=='P') pos[++stot]=now;
        else if (s[i]=='B') now=fa[now];
        else { int w=s[i]-'a';
            if (!ch[now][w]) ch[now][w]=++tot,fa[tot]=now;
            now=ch[now][w];
        }
    }
}
inline void getfail() { queue<int> Q;
    for (re int i=0;i<26;++i) if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re 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];
        }
    }
}

int st[N],ed[N],tim=0;
inline void dfs(int u) {
    st[u]=++tim;
    for (re int i=head[u];i;i=e[i].nxt) dfs(e[i].v);
    ed[u]=tim;
}

int c[N];
inline void add(int x,int y) { for (;x<=tim;x+=x&-x) c[x]+=y; }
inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

struct query { int x,id; };
vector<query> Q[N];

char s[N]; int ans[N];
int main() {
    scanf("%s",s+1); int l=strlen(s+1);
    insert(s,l); getfail();
    for (re int i=1;i<=tot;++i) addEdge(fail[i],i);
    dfs(0);
    int m=read();
    for (re int i=1;i<=m;++i) {
        int x=read(),y=read();
        Q[y].push_back((query){x,i});
    }
    add(st[0],1);
    for (re int i=1,now=0,num=0;i<=l;++i) {
        if (s[i]=='P') { ++num;
            for (re auto j:Q[num]) { int u=pos[j.x];
                ans[j.id]=sum(ed[u])-sum(st[u]-1);
            }
        }
        else if (s[i]=='B') add(st[now],-1),now=fa[now];
        else now=ch[now][s[i]-'a'],add(st[now],1);
    }
    for (re int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}