AC自动机 + 树状数组

这道题暴力把询问离线排序之后，直接用AC自动机找答案可以拿到70分。。

正解应该是考虑fail树和trie树父亲节点的意义。

题目是让我们求第x个单词在第y个中出现了多少次，我们先看第y个单词在trie中的意义。

假设第y个单词在trie中以p节点结尾，那么p节点的父亲节点（包括p节点自己）到根组成的串均为y的前缀。

而这些节点的fail指针指向的节点代表什么呢？假设p的父亲节点a他的fail指针指向b，那么意思是 以b结尾的单词是y这个单词的前缀（根到a是y这个单词的一个前缀）的一个后缀。

前缀的后缀显然就是子串，也就是在y中出现过的串。

那么a这个点的fail树上的祖先节点显然全在y中出现过。

所以我们只要统计每一个y，他在trie中的父亲节点有几个是fail树中x的子节点就行啦。

所以我们先dfs一遍fail树，把fail树映射成序列，再dfs一次trie，对经过的每个节点+1，回溯时-1，计算答案的时候，只要用树状数组辅助查询区间和就好了。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;using LL = long long;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}template 
     
      inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }template 
      
       inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 100005;string t;int n, tot, cnt, trie[N][26], fa[N], ending[N], fail[N], idx[N], k, head[N], dfn[N], c, size[N], tree[N];int x, y, ans[N], tr[N][26];struct Edge { int v, next; } edge[N<<1];vector
       
        
         > Q[N];inline void add(int k, int val){    for(; k <= c; k += lowbit(k)) tree[k] += val;}inline int query(int k){    int ret = 0;    for(; k; k -= lowbit(k)) ret += tree[k];    return ret;}void addEdge(int a, int b){    edge[k].v = b, edge[k].next = head[a], head[a] = k ++;}void getFail(){    queue
         
           q; for(int i = 0; i < 26; i ++){ if(trie[0][i]){ tr[0][i] = trie[0][i]; q.push(trie[0][i]); } } while(!q.empty()){ int s = q.front(); q.pop(); for(int i = 0; i < 26; i ++){ if(trie[s][i]){ tr[s][i] = trie[s][i]; fail[trie[s][i]] = trie[fail[s]][i]; q.push(trie[s][i]); } else trie[s][i] = trie[fail[s]][i]; } }}void dfs(int s, int fa){ dfn[s] = ++ c, size[s] = 1; for(int i = head[s]; i != -1; i = edge[i].next){ int u = edge[i].v; if(u == fa) continue; dfs(u, s); size[s] += size[u]; }}void match(int s){ add(dfn[s], 1); if(ending[s]){ for(auto &p: Q[s]){ int x = p.first, y = p.second; ans[y] = query(dfn[x] + size[x] - 1) - query(dfn[x] - 1); } } for(int i = 0; i < 26; i ++){ if(tr[s][i]) match(tr[s][i]); } add(dfn[s], -1);}int main(){ __fastIn; cin >> t >> n; int p = 0; for(int i = 0; i < t.size(); i ++){ if(t[i] >= 'a' && t[i] <= 'z'){ int ch = t[i] - 'a'; if(!trie[p][ch]) trie[p][ch] = ++ tot, fa[tot] = p; p = trie[p][ch]; } else if(t[i] == 'B') p = fa[p]; else ending[p] = ++cnt, idx[cnt] = p; } getFail(); full(head, -1); for(int i = 1; i <= tot; i ++){ addEdge(fail[i], i), addEdge(i, fail[i]); } dfs(0, 0); for(int i = 1; i <= n; i ++){ cin >> x >> y; Q[idx[y]].emplace_back(idx[x], i); } match(0); for(int i = 1; i <= n; i ++){ cout << ans[i] << endl; } return 0;}