参考
csfnb的博客
题意
给定一个包含小写字母、‘B’、'P’的操作序列，小写字母表示向栈中压入本字母，'B’表示弹出栈顶字母，'P’表示打印当前栈中的字符串（不出栈）。之后有m个询问，每次给出两个数x和y，问第x个打印的字符串在第y次打印的字符串中出现了多少次。
做法
首先对操作序列建AC自动机，标记每次打印的终结位置。由AC自动机的性质可得，第x个打印的字符串在第y次打印的字符串中出现的次数就等于 fail树中以x终结点为根的的子树 与 trie树中0到y终结点的路径 的交集大小。
如何求解这个交集？在树上dfs时，进入一个节点时给它的值+1，退出一个节点时给它的值-1，这样整棵树中只有根到当前节点的路径上有值，此时求一个子树的交集大小就转变成了子树值求和问题。
将所有询问离线，问题在trie树的dfs过程中就变成了【单点修改，子树求和】问题，再对fail树求dfs序，问题就变成了【单点修改，区间求和】问题，使用树状数组求解即可。
代码
#include <bits/stdc++.h>
using namespace std
; using ll
= long long; inline int read();
const int M
= 100016, MOD
= 1000000007;
char str
[M
];
int ans
[M
];
vector
<pair
<int,int>> save
[M
];
int id
[M
];
struct Tree
{
vector
<int> son
[M
];
void addEdge(int u
, int v
)
{
son
[u
].push_back(v
);
}
int st
[M
], ed
[M
], cnt
;
void dfs(int u
)
{
st
[u
] = ++cnt
;
for(int v
:son
[u
]) dfs(v
);
ed
[u
] = cnt
;
}
void build()
{
cnt
= 0;
dfs(0);
}
int bit
[M
];
void modify(int p
, int x
)
{
p
= st
[p
];
for(;p
<=cnt
;p
+=p
&-p
) bit
[p
]+=x
;
}
int sum(int p
)
{
int res
= 0;
for(;p
;p
-=p
&-p
) res
+= bit
[p
];
return res
;
}
int query(int u
)
{
int l
= st
[u
], r
= ed
[u
];
return sum(r
) - sum(l
-1);
}
}tree
;
struct Aho_Corasick_Automaton
{
int ch
[M
][26], fa
[M
], fail
[M
], dep
[M
], sz
;
void insert(const char *s
)
{
int u
= 0, cnt
= 0;
for(int i
= 0; s
[i
]; i
++)
{
if(islower(s
[i
]))
{
int &v
= ch
[u
][s
[i
] - 'a'];
if(!v
)
{
v
= ++sz
;
fa
[v
] = u
;
dep
[v
] = dep
[u
] + 1;
}
u
= v
;
}
else if(s
[i
]=='B')
{
u
= fa
[u
];
}
else if(s
[i
]=='P')
{
id
[++cnt
] = u
;
}
}
}
void build()
{
queue
<int> q
;
for(int v
:ch
[0]) if(v
)
{
fail
[v
] = 0;
tree
.addEdge(fail
[v
], v
);
q
.push(v
);
}
while(!q
.empty())
{
int u
= q
.front(); q
.pop();
for(int i
= 0; i
< 26; i
++)
{
int &v
= ch
[u
][i
];
if(v
)
{
fail
[v
] = ch
[fail
[u
]][i
];
tree
.addEdge(fail
[v
], v
);
q
.push(v
);
}
else v
= ch
[fail
[u
]][i
];
}
}
tree
.build();
}
void dfs(int u
)
{
tree
.modify(u
, 1);
for(auto q
:save
[u
])
ans
[q
.second
] = tree
.query(q
.first
);
for(int v
:ch
[u
]) if(dep
[v
]>dep
[u
])
dfs(v
);
tree
.modify(u
,-1);
}
void query()
{
dfs(0);
}
}AC
;
int main(void)
{
#ifdef _LITTLEFALL_
freopen("in.txt","r",stdin);
#endif
scanf("%s",str
);
AC
.insert(str
);
int m
= read();
for(int i
=1; i
<=m
; ++i
)
{
int pat
= id
[read()], tex
= id
[read()];
save
[tex
].emplace_back(pat
, i
);
}
AC
.build();
AC
.query();
for(int i
=1;i
<=m
;++i
)
printf("%d\n",ans
[i
] );
return 0;
}
inline int read(){
int x
=0,f
=1;char ch
=getchar();
while(ch
<'0'||ch
>'9') {if(ch
=='-')f
=-1;ch
=getchar();}
while(ch
>='0'&&ch
<='9'){x
=x
*10+ch
-'0';ch
=getchar();}
return x
*f
;
}
