题意：以trie的形式给出n个字符串，每次询问第x个字符串在第y个字符串中出现了几次。
解：总串长是n2级别的，所以不能用什么后缀自动机...
[update]可以建triesam但是不知道trie上的一个节点对应到了sam上的哪几个节点...感觉可以做...好混乱
听说是个AC自动机上DP，然后怎么想状态都是n²的，然后看题解发现跟DP没啥关系...
是这样的：对于x在y中出现的每一次，我们把它的前面一直补齐，这样每个串就对应着y的一个前缀，且这个前缀的一个后缀是x。
可知，trie上y节点到根的链就代表这些前缀。
然后要求后缀是x。因为x也在这些串中出现了，所以这些前缀一直跳fail的话一定会跳到x节点。即他们全都在x的fail树的子树中。
然后我们就发现，trie上y到根的路径上的节点和fail树上x的子树的节点的交就是答案。
一个很朴素的想法就是把这两棵树剖出来，就是一个二维数点问题。把主席树建出来，因为用了树剖所以每次回答询问是nlog²n的，可以做到在线。
一个高端想法就是离线下来，按照fail树建DFS序。在trie上DFS，维护trie树上当前节点到根的路径权值为1，别的地方为0。
然后查询就是当在trie上DFS到y的时候，查询x在fail树中的子树权值和。
这是单点修改，区间查询。树状数组即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector> const int N = ; struct Edge {
int nex, v;
}edge[N << ]; int top; struct Node {
int x, y, ans;
}node[N]; int tr[N][], fail[N], tot = ;
char str[N];
int ed[N], e[N], pos[N], siz[N], num;
std::vector<int> v[N]; namespace bit {
int ta[N];
inline void add(int p) {
for(int i = p; i < N; i += i & (-i)) {
ta[i]++;
}
return;
}
inline void del(int p) {
for(int i = p; i < N; i += i & (-i)) {
ta[i]--;
}
return;
}
inline int getSum(int p) {
int ans = ;
for(int i = p; i >= ; i -= i & (-i)) {
ans += ta[i];
}
return ans;
}
inline int ask(int l, int r) {
return getSum(r) - getSum(l - );
}
} inline void add(int x, int y) {
top++;
edge[top].v = y;
edge[top].nex = e[x];
e[x] = top;
return;
} inline void getAC() {
std::stack<int> S;
std::queue<int> Q;
int n = strlen(str), t = , p = ;
for(int i = ; i < n; i++) {
if(str[i] == 'P') {
ed[++t] = p;
continue;
}
if(str[i] == 'B') {
if(!S.empty()) {
p = S.top();
S.pop();
}
continue;
}
int f = str[i] - 'a';
if(!tr[p][f]) {
tr[p][f] = ++tot;
}
S.push(p);
p = tr[p][f];
}
// getfail
fail[] = ;
Q.push();
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int f = ; f < ; f++) {
if(!tr[x][f]) {
continue;
}
int y = tr[x][f], j = fail[x];
while(!tr[j][f] && j != ) {
j = fail[j];
}
if(tr[j][f] && x != ) {
j = tr[j][f];
}
fail[y] = j;
add(j, y);
Q.push(y);
}
}
return;
} void DFS_1(int x) {
pos[x] = ++num;
siz[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
DFS_1(y);
siz[x] += siz[y];
}
return;
} void DFS_2(int x) {
bit::add(pos[x]);
for(int i = ; i < v[x].size(); i++) {
int t = node[v[x][i]].x;
node[v[x][i]].ans = bit::ask(pos[ed[t]], pos[ed[t]] + siz[ed[t]] - );
}
for(int i = ; i < ; i++) {
if(tr[x][i]) {
DFS_2(tr[x][i]);
}
}
bit::del(pos[x]);
return;
} int main() {
scanf("%s", str);
//
getAC();
DFS_1();
int m;
scanf("%d", &m);
for(int i = ; i <= m; i++) {
scanf("%d%d", &node[i].x, &node[i].y);
v[ed[node[i].y]].push_back(i);
} DFS_2(); for(int i = ; i <= m; i++) {
printf("%d \n", node[i].ans);
}
return ;
}
AC代码