洛谷P2414 [NOI2011]阿狸的打字机(AC自动机fail树上维护树状数组)

题意：

按输入串\(s\)建\(AC\)自动机即可。
\('B'\)相当于在\(trie\)树上从\(u\)点回退到\(u\)的父亲，遇到\('P'\)用\(vis\)数组记录一下当前串在\(trie\)的位置。

分析：

此题可考虑离线询问，每遍历题目所给的字符串的一个\(P\)，就计算这个\(P\)代表第\(y\)个串的贡献，比如遍历到第二个\(P\)，则解决所有\((x,2)\)的询问，如果有的话。
如何计算第\(x\)个串在第\(y\)个串出现的次数：
先将自动机的\(fail\)树建好，然后在\(trie\)上向下走\(s\)串，每走过一个节点，就让这个节点在\(fail\)树上的节点到\(fail\)树上的根这条路径出现的串的次数通通加\(1\)。
不难发现在\(fail\)树上，\(u\)节点到根节点的所有串都是\(u\)的后缀，反过来也就是说\(u\)节点的祖先都是\(u\)的子串。那么如果在\(trie\)树上走到\(u\)点有询问要处理，我们查询\(x\)串在\(fail\)树上对应的节点的子树的串的出现次数就好了（\(x\)串肯定是其子树的任意一个串的子串）。查询子树和\(dfs\)序用树状数组维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

const int N = 100000 + 5;

int q, x, y;
int tot, num, len, vis[N], ch[N][26], pre[N], fail[N];
int cur, dfn[N], edfn[N];
int bit[N], ans[N];
char s[N];
vector<int> g[N];
vector<pair<int, int> > v[N];

void init() {
    len = strlen(s);
    int u = 0, p, f;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'B') {
            u = pre[u];
        } else if (s[i] == 'P') {
            vis[++num] = u;
        } else {
            p = s[i] - 'a';
            if (!ch[u][p]) ch[u][p] = ++tot;
            f = u;
            u = ch[u][p];
            pre[u] = f;
        }
    }
}

void getfail() {
    queue<int> q;
    for (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 (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];
            }
        }
    }
}

void dfs(int u) {
    dfn[u] = ++cur;
    for (auto v : g[u]) {
        dfs(v);
    }
    edfn[u] = cur;
}

void update(int x, int w) {
    for (int i = x; i <= cur; i += (i & -i)) bit[i] += w;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= (i & -i)) res += bit[i];
    return res;
}

void solve() {
    int u = 0, k = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'B') {
            update(dfn[u], -1);
            u = pre[u];
        } else if (s[i] == 'P'){
            ++k;
            for (auto it : v[k]) {
                ans[it.se] = query(edfn[vis[it.fi]]) - query(dfn[vis[it.fi]] - 1);
            }
        } else {
            u = ch[u][s[i] - 'a'];
            update(dfn[u], 1);
        }
    }
}

int main() {
    scanf("%s", s);
    init();
    getfail();
    for (int i = 1; i <= tot; i++) g[fail[i]].pb(i);
    dfs(0);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d %d", &x, &y);
        v[y].pb(mp(x, i));
    }
    solve();
    for (int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}