题意
给你一些字符串。\(m\)次询问，每一次询问第\(x\)个字符串在\(y\)字符串中出现了多少次。（输入总长$ \le 10^5$, \(M \le 10^5\)）
分析
在ac自动机上，\(x\)字符串出现的所有位置就是其它节点的fail树上有这个节点的节点。即fail树中，\(x\)字符串终止节点的子树。
题解
根据分析，我们只要构造ac自动机和fail树，按dfs序依次便历ac自动机，将节点到根的路径打上标记。每到一个终止节点，就更新以这个节点为模板的匹配串的答案，即这些节点子树的和。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char buf[20*N], *is=buf;
int ihead[N], cnt, last[N], c[N][26], fail[N], pos[N], FF[N], LL[N], tot, su[N], ans[N];
inline bool isdig(const char &c) {
return c>='0'&&c<='9';
}
inline bool isok(const char &c) {
return (c>='a'&&c<='z')||c=='P'||c=='B';
}
inline int getint() {
register int x=0;
for(; !isdig(*is); ++is);
for(; isdig(*is); ++is) {
x=x*10+*is-48;
}
return x;
}
inline void putint(int x) {
if(x==0) {
*is++='0';
}
else {
static int s[10], top;
for(top=0; x; x/=10) s[++top]=x%10;
while(top) {
*is++=s[top--]+'0';
}
}
*is++='\n';
}
struct E {
int next, to, id;
}e[N];
inline void add(int x, int y, int id=-1) {
e[++cnt]=(E){ihead[x], y, id}; ihead[x]=cnt;
}
inline void adds(int x, int s) {
for(; x<=tot; x+=x&-x) {
su[x]+=s;
}
}
inline int sum(int x) {
int y=0;
for(; x; x-=x&-x) {
y+=su[x];
}
return y;
}
inline void bfs() {
static int q[N], fr, ta;
fr=ta=0;
q[ta++]=0;
while(fr!=ta) {
int x=q[fr++];
for(int ch=0; ch<26; ++ch) {
if(c[x][ch]) {
int y=c[x][ch];
q[ta++]=y;
if(x==0) {
add(0, y);
continue;
}
fail[y]=c[fail[x]][ch];
add(fail[y], y);
}
else {
c[x][ch]=c[fail[x]][ch];
}
}
}
}
inline void dfs(int x) {
static int fid=0;
FF[x]=++fid;
for(int i=ihead[x]; i; i=e[i].next) {
dfs(e[i].to);
}
LL[x]=fid;
}
inline void getans(int x) {
adds(FF[x], 1);
for(int i=ihead[x]; i; i=e[i].next) {
int y=e[i].to;
ans[e[i].id]=sum(LL[y])-sum(FF[y]-1);
}
for(int ch=0; ch<26; ++ch) {
if(c[x][ch] && (x==0 || c[x][ch]!=c[fail[x]][ch])) {
getans(c[x][ch]);
}
}
adds(FF[x], -1);
}
void init() {
fread(buf, 1, sizeof buf, stdin);
for(; !isok(*is); ++is);
int now=0, n=0, len=0;
for(; isok(*is); ++is) {
if(*is=='P') {
pos[++n]=now;
}
else if(*is=='B') {
now=last[len--];
}
else {
int ch=*is-'a';
if(!c[now][ch]) {
c[now][ch]=++tot;
}
last[++len]=now;
now=c[now][ch];
}
}
bfs();
dfs(0);
}
int main() {
init();
memset(ihead, 0, sizeof(int)*(tot+1));
cnt=0;
int m=getint();
for(int i=0; i<m; ++i) {
int x, y;
x=getint();
y=getint();
add(pos[y], pos[x], i);
}
++tot;
getans(0);
is=buf;
for(int i=0; i<m; ++i) {
putint(ans[i]);
}
fwrite(buf, 1, sizeof(char)*(is-buf), stdout);
return 0;
}