Description：

一个打字机，每次执行在当前字符串后添加一个字符，删除当前字符串最后一个字符，将当前字符串加入字符串集中三种操作中的一个。在最后多次询问字符串集中第 $i$ 个字符串在第 $j$ 个字符串中出现了几次。

$1\le N\le 100000$

Solution：

对字符串集建立 $AC$ 自动机， $trie$ 树上某个点的 $fail$ 表示最长的前缀 $=$ 后缀，那么一个点在 $fail$ 树中的子树即表示这个点表示的字符串是 $trie$ 树中哪些节点表示的字符串的后缀，由于一个子串一定是某个前缀的后缀，那么对于一个询问 $(i,j)$ ，把根到 $j$ 的路径上的点都打上标记，那么只要查询 $fail$ 树上以 $i$ 为根的子树中有多少个点打上了标记，用线段树维护 $fail$ 树的 $dfs$ 序，在 $trie$ 树上 $dfs$ ，进入节点时给这个点打标记，退出时恢复标记，则任意时刻打了标记的点是一条从根到这个点的链，离线查询所有这个点作为 $j$ 的询问即可。

注意由于建 $trie$ 图破坏了 $trie$ 树的结构，开一个数组保存 $trie$ 树的 $dfs$ 序，建树时暴力插入会 $T$ ，在 $trie$ 树上维护一个 $fa$ ，则退格表示爬 $fa$ ，加字符表示向下走，时间空间都是 $O(N)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int m;

char str[100010];

int l;

#define MAXN 100010

#define rint register int

char ch[MAXN];

int to[MAXN];

int tot = 0;

string s[MAXN];

struct node

{

    int c[26],fail,fa;

    bool w;

}t[MAXN];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root = 0;

inline void insert(int l,int id)

{

    int cur = root;

    for(rint i = 1;i <= l;++i)

    {

        if(t[cur].c[ch[i] - 'a'] == 0)

            t[cur].c[ch[i] - 'a'] = newnode();

        cur = t[cur].c[ch[i] - 'a'];

    }

    t[cur].w = true;

    to[id] = cur;

    return;

}

inline void init()

{

    char c = getchar();

    int l = 0;

    while(isalpha(c))

    {

    	str[++l] = c;

        c = getchar();

    }

    int cur = root;

    for(rint i = 1;i <= l;++i)

    {

        if(str[i] == 'P')

        {

            t[cur].w = true;

            to[++tot] = cur;

        }

        if(str[i] == 'B')

        {

            cur = t[cur].fa;

        }

        if(islower(str[i]))

        {

            if(t[cur].c[str[i] - 'a'] == 0)

            {

                t[cur].c[str[i] - 'a'] = newnode();

                t[t[cur].c[str[i] - 'a']].fa = cur;

            }

            cur = t[cur].c[str[i] - 'a'];

        }

    }

    return;

}

int cmp[MAXN << 1],now = 0;

inline void pre(int k)

{

    cmp[++now] = k;

    for(rint i = 0;i < 26;++i)

    {

        if(t[k].c[i] == 0)continue;

        pre(t[k].c[i]);

    }

    cmp[++now] = -k;

    return;

}

inline void getfail()

{

    queue<int> q;

    for(rint i = 0;i < 26;++i)

    {

        if(t[root].c[i] != 0)

        {

            t[t[root].c[i]].fail = root;

            q.push(t[root].c[i]);

        }

    }

    while(!q.empty())

    {

        rint k = q.front();q.pop();

        for(rint i = 0;i < 26;++i)

        {

            if(t[k].c[i] != 0)

            {

                int p = t[k].fail;

                while(p && t[p].c[i] == 0)p = t[p].fail;

                t[t[k].c[i]].fail = t[p].c[i];

                q.push(t[k].c[i]);

            }

            else

            {

                t[k].c[i] = t[t[k].fail].c[i];

            }

        }

    }

    return;

}

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

inline void build()

{

    for(rint i = 1;i <= ptr;++i)

    {

        add(t[i].fail,i);

    }

    return;

}

struct question

{

    int to,nxt,ans;

}q[MAXN];

int qt[MAXN] = {0};

int qs = 0;

inline void addq(int a,int b)

{

    ++qs;q[qs].to = b;q[qs].nxt = qt[a];qt[a] = qs;

    return;

}

int read()

{

    int res = 0;

    char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

inline void ask()

{

    m = read();

    int a,b;

    for(rint i = 1;i <= m;++i)

    {

        a = read();b = read();

        addq(to[b],to[a]);

    }

    return;

}

int rank[MAXN],th[MAXN],siz[MAXN],n = 0;

void dfs(int k)

{

    siz[k] = 1;

    rank[k] = ++n;

    th[n] = k;

    for(rint i = lin[k];i != 0;i = e[i].nxt)

    {

        dfs(e[i].to);

        siz[k] += siz[e[i].to];

    }

    return;

}

namespace tree

{

    struct segment

    {

        int lc,rc,sum;

        segment(){sum = 0;}

    }t[MAXN << 1];

    int ptr = 0;

    inline int newnode(){return ++ptr;}

    int root;

    void build(int &rt,int l,int r)

    {

        rt = newnode();

        if(l == r)return;

        rint mid = ((l + r) >> 1);

        build(t[rt].lc,l,mid);

        build(t[rt].rc,mid + 1,r);

        return;

    }

    void add(int rt,int p,int k,int l,int r)

    {

        if(l == r)

        {

            t[rt].sum += k;

            return;

        }

        rint mid = ((l + r) >> 1);

        if(p <= mid)add(t[rt].lc,p,k,l,mid);

        else add(t[rt].rc,p,k,mid + 1,r);

        t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

        return;

    }

    int query(int rt,int L,int R,int l,int r)

    {

        if(L <= l && r <= R)

        {

            return t[rt].sum;

        }

        rint mid = ((l + r) >> 1);

        int res = 0;

        if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

        if(R >= mid + 1)res += query(t[rt].rc,L,R,mid + 1,r);

        return res;

    }

}

inline void query()

{

    for(rint k = 1;k <= now;++k)

    {

        if(cmp[k] == 0)continue;

        if(cmp[k] > 0)

        {

            tree::add(tree::root,rank[cmp[k]],1,1,n);

            for(rint i = qt[cmp[k]];i != 0;i = q[i].nxt)

            {

                q[i].ans = tree::query(tree::root,rank[q[i].to],rank[q[i].to] + siz[q[i].to] - 1,1,n);

            }

        }

        else

        {

            tree::add(tree::root,rank[-cmp[k]],-1,1,n);

        }

    }

    for(rint i = 1;i <= qs;++i)

    {

        printf("%d\n",q[i].ans);

    }

    return;

}

int main()

{

    init();

    pre(0);

    getfail();

    build();

    ask();

    dfs(0);

    tree::build(tree::root,1,n);

    query();

    return 0;

}