命題

给定$n$个字符串，$m$个询问$(x,y)$表示询问第$x$个字符串在第$y$个字符串中出现的次数。

---

对于只考虑完整的字符串之间的匹配的问题，因为涉及不到子串，所以大可不必使用后缀数据结构。我们对所有字符串建立一个AC自动机，然后思考fail指针的意义：

指向当前状态的所有后缀中最长的一个后缀满足该后缀可以在自动机上找到对应的状态。

如果把这个后缀看为$x$，当前状态为$y$，则这一组$(x,y)$恰好满足命题要求。

引理

所有节点及除根节点之外的fail指针构成的图是一颗树。

證明：每个状态节点有一条出边且边数比点数少一个，满足该图是一颗树的充要条件。

对于一个询问$Q=(x,y)$，当我们从根运行到$y$所在的状态，所经过的节点中fail指针指向$x$的个数即为询问的答案。所以我们对于每一个$y$离线处理，将所有与之有关的$x$挂链，统计答案时利用dfs序+区间数据结构动态维护子树的权值和。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#pragma GCC optimize("-O3")
using namespace std;
#define foreach(x) for(__typeof__(x.begin()) it = x.begin(); it != x.end(); it++)
typedef long long ll;
template <typename _Tp>
__inline void read(_Tp &a, char c = 0) {
    for (c = getchar(); !isdigit(c); c = getchar());
    for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}
const int N = 1e5 + 5;
struct node { int nxt[26], fa, fail; } tr[N];
int root = 1, tot = 1, num = 0, pos[N], id[N], q[N], head, tail = -1;
char str[N];
int hd[N], nxt[N], to[N], _tot;
__inline void add(int a, int b) { nxt[++_tot] = hd[a], to[hd[a] = _tot] = b; }
__inline void null() {}
__inline int build(char *s) {
    register int p = root, len = strlen(s), x;
    tr[root].fa = root;
    for (int i = 0; i < len; i++) {
        x = s[i] - 'a';
        if (s[i] == 'B') p = tr[p].fa;
        else if (s[i] == 'P')  pos[++num] = p, id[p] = num;
        else {
            if (!tr[p].nxt[x]) tr[p].nxt[x] = ++tot, tr[tot].fa = p;
            p = tr[p].nxt[x];
        }
    } p = root;
    for (int i = 0; i < 26; i++) {
        if (tr[p].nxt[i] == 0) continue;
        tr[tr[p].nxt[i]].fail = root;
        q[++tail] = tr[p].nxt[i];
        add(root, tr[p].nxt[i]);
    }
    while (head <= tail) {
        p = q[head++];
        for (int i = 0; i < 26; i++) {
            if (tr[p].nxt[i]) {
                int x = tr[p].nxt[i], j = tr[p].fail;
                while (j != root && tr[j].nxt[i] == 0) j = tr[j].fail;
                if (tr[j].nxt[i]) j = tr[j].nxt[i];
                tr[x].fail = j, add(j, x), q[++tail] = x;
            }
        }
    } return root;
}
int st[N], ed[N], TIME;
int a[N], ans[N], n, vis[N];
struct data { int x, q_id; } d;
vector<data> s[N];
__inline int lowbit(int x) { return x & -x; }
__inline void __add(int pos, int val) { /*printf("add(%d, %d)\n", pos, val);*/ for (int i = pos; i <= TIME; i += lowbit(i)) a[i] += val; }
__inline int __ask(int pos) { /*printf("ask(%d)\n", pos);*/ int ret = 0; for (int i = pos; i; i -= lowbit(i)) ret += a[i]; return ret; }
__inline int ask(int l, int r) { return __ask(r) - __ask(l - 1); }
__inline int dfs(int u) {
    st[u] = ed[u] = ++TIME;
    // printf("at %d with time = %d\n", u, TIME);
    for (int v, e = hd[u]; e; e = nxt[e]) v = to[e], ed[u] = dfs(v); return ed[u];
}
__inline void dfs_ac(int u) {
    __add(st[u], 1);
    if (vis[id[u]]) foreach (s[id[u]]) d = *it, ans[d.q_id] = ask(st[pos[d.x]], ed[pos[d.x]]);
    for (int v, i = 0; i < 26; i++)  (v = tr[u].nxt[i]) ? dfs_ac(v) : null(); __add(st[u], -1);
}
__inline int* procedure(int root) {
    dfs(root); //print();
    for (int i = 0; i < 26; i++) if (tr[root].nxt[i]) dfs_ac(tr[root].nxt[i]);
    return ans;
}
__inline char* input() {
    scanf("%s", str), read(n);
    register int x, y;
    for (int i = 1; i <= n; i++) read(x), read(y), s[y].push_back((data) { x, i }), vis[y] = true;
    return str;
}
__inline void output(int ans[]) { for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); }
int main() { return output(procedure(build(input()))), 0; }
Code language: PHP (php)