题目

思路

将每一个输出的串放入一个 Trie 树中。

考虑离线处理询问 \((x, y)\)，对于每一个 \(y\) 集中处理所有的 \(x\)，沿着 \(y\) 的字符在 Trie 树上走，走过的点标记一下，结果就是 \(x\) 字符串结尾节点在 fail 树上的对应节点的子树的标记数量，记得在节点离开的时候撤销标记。

为了方便统计子树信息，我们使用类似树链剖分的方法对点重新编号再使用线段树进行维护即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 2600010;

struct edge {
    int to, next;
} e[M];

int head[M], idx = 1;

void add(int u, int v) {
    idx++;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx;
}

string opt_str;
int q, ans[N];
vector<pair<int, int> > query[N];

struct ac {
    int son[26];
    int fa;
    int fail;
} t[N];

int ac_idx;
int val[N];

void insert() {
    int p = 0, str_idx = 0;
    for (auto x : opt_str) {
        if (x >= 'a' && x <= 'z') {
            int u = x - 'a';
            if (!t[p].son[u]) t[p].son[u] = ++ac_idx;
            t[t[p].son[u]].fa = p;
            p = t[p].son[u];
        }
        else if (x == 'B') p = t[p].fa;
        else {
            str_idx++;
            val[str_idx] = p;
        }
    }
}

void getfail() {
    queue<int> q;

    for (int i = 0; i < 26; i++) {
        if (t[0].son[i]) {
            q.push(t[0].son[i]);
        }
    }

    while (q.size()) {
        int g = q.front();
        q.pop();

        for (int i = 0; i < 26; i++) {
            if (t[g].son[i]) {
                t[t[g].son[i]].fail = t[t[g].fail].son[i];
                q.push(t[g].son[i]);
            }
            else t[g].son[i] = t[t[g].fail].son[i];
        }
    }
    for (int i = 1; i <= ac_idx; i++) add(t[i].fail, i);
}

int dfn[N], sz[N], dfn_idx;

void dfs(int u, int fa) {
    sz[u] = 1, dfn[u] = ++dfn_idx;
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs(to, u);
        sz[u] += sz[to];
    }
}

int tr[N];

void modify(int u, int x) {
    if (u <= 0) return;
    for (; u < N; u += u & -u) {
        tr[u] += x;
    }
}

int ask(int u) {
    if (u <= 0) return 0;
    int ans = 0;
    for (; u; u -= u & -u) ans += tr[u];
    return ans;
}

void getans() {
    int p = 0, str_idx = 0;
    for (auto x : opt_str) {
        if (x >= 'a' && x <= 'z') {
            int u = x - 'a';
            p = t[p].son[u];
            modify(dfn[p], 1);
        }
        else if (x == 'B') {
            modify(dfn[p], -1);
            p = t[p].fa;
        }
        else {
            str_idx++;
            for (auto [x, y] : query[str_idx]) {
                int ver = val[x];
                ans[y] = ask(dfn[ver] + sz[ver] - 1) - ask(dfn[ver] - 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> opt_str >> q;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        query[r].push_back({l, i});
    }

    insert();
    getfail();
    dfs(0, 0);
    getans();

    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}