Description

阿狸喜欢收藏各种稀奇古怪的东西, 最近他淘到一台老式的打字机. 打字机上只有 28 个按键, 分别印有 \(26\) 个小写英文字母和 ‘B’、‘P’ 两个字母.

经阿狸研究发现, 这个打字机是这样工作的:

  1. 输入小写字母, 打字机的一个凹槽中会加入这个字母 (这个字母加在凹槽的最后).
  2. 按一下印有 ‘B’ 的按键, 打字机凹槽中最后一个字母会消失.
  3. 按一下印有 ‘P’ 的按键, 打字机会在纸上打印出凹槽中现有的所有字母并换行, 但凹槽中的字母不会消失.

例如, 阿狸输入 aPaPBbP, 纸上被打印的字符如下:

a

aa

ab

我们把纸上打印出来的字符串从 \(1\) 开始顺序编号, 一直到 \(n\). 打字机有一个非常有趣的功能, 在打字机中暗藏一个带数字的小键盘, 在小键盘上输入两个数 \((x, y)\) (其中 \(1 \leq x, y \leq n\)) , 打字机会显示第 \(x\) 个打印的字符串在第 \(y\) 个打印的字符串中出现了多少次.

阿狸发现了这个功能以后很兴奋, 他想写个程序完成同样的功能, 你能帮助他么?

Input

输入的第一行包含一个字符串, 按阿狸的输入顺序给出所有阿狸输入的字符.

第二行包含一个整数 \(m\), 表示询问个数.

接下来 \(m\) 行描述所有由小键盘输入的询问. 其中第 \(i\) 行包含两个整数 \(x, y\), 表示 第 \(i\) 个询问为 \((x, y)\).

Output

输出 \(m\) 行, 其中第 \(i\) 行包含一个整数, 表示第 \(i\) 个询问的答案.

Sample Input

aPaPBbP
3
1 2
1 3
2 3

Sample Output

2
1
0

Data Range

对于所有数据, 满足 \(1 \leq n, m \leq 10^5\), 且输入总长 \(\leq 10^5\)

Explanation

这道题可以直接在 AC 自动机上的 Fail 树上瞎搞打标记~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>

using namespace std;
typedef long long lli;
const int maxn = 100100;

class AhoCorasickAutomaton
{
public:
    struct node
    {
        node *ch[27], *par, *fail;
        vector<node*> next;
        int val, end, dfn;
    };
    node *root, npool[maxn];
    int ncnt;
    node* make_node(int val)
    {
        node *p = &npool[++ncnt];
        memset(p->ch, 0, sizeof(p->ch));
        p->par = p->fail = NULL;
        p->val = val; p->end = p->dfn = 0;
        return p;
    }
    int m; // How many strings
    void build_tree(int n, char str[])
    {
        root = make_node(0);
        // Static-like insertion of strings
        stack<node*> stk;
        stk.push(root);
        this->m = 0;
        for (int i = 1; i <= n; i++) {
            if (str[i] == 'B') {
                stk.pop();
            } else if (str[i] == 'P') {
                node *p = stk.top();
                p->end = ++m;
            } else {
                int ch = str[i] - 'a';
                node *p = stk.top();
                if (!p->ch[ch]) {
                    p->ch[ch] = make_node(ch);
                    p->ch[ch]->par = p;
                }
                stk.push(p->ch[ch]);
            }
        }
        // Creating *fail pointers, and its tree
        queue<node*> que;
        for (int i = 0; i < 26; i++) if (root->ch[i]) {
            root->ch[i]->fail = root;
            root->next.push_back(root->ch[i]);
            que.push(root->ch[i]);
        }
        while (!que.empty()) {
            node *p = que.front();
            que.pop();
            for (int i = 0; i < 26; i++) if (p->ch[i]) {
                node *q = p->fail;
                while (q != root && !q->ch[i])
                    q = q->fail;
                if (q->ch[i])
                    q = q->ch[i];
                p->ch[i]->fail = q;
                q->next.push_back(p->ch[i]);
                que.push(p->ch[i]);
            }
        }
        this->dfn = 0;
        return ;
    }
    // Really processing the results below.
    int dfn;
    int start[maxn], end[maxn]; // DFN begin and end of each node, on fail tree
    void dfs(node *p)
    {
        vector<node*>::iterator itert;
        p->dfn = ++dfn;
        if (p->end > 0)
            start[p->end] = dfn;
        for (itert = p->next.begin(); itert != p->next.end(); itert++)
            dfs(*itert);
        if (p->end > 0)
            end[p->end] = dfn;
        return ;
    }
    /********** These belong to the the Tree-Style Array **********/
    /*****/ int tsa[maxn];
    /*****/ void change(int x, int val) {
    /*****/     for (; x <= dfn; x += x & -x)
    /*****/         tsa[x] += val;
    /*****/     return ; }
    /*****/ int query(int x) {
    /*****/     int res = 0;
    /*****/     for (; x > 0; x -= x & -x)
    /*****/         res += tsa[x];
    /*****/     return res; }
    /********** Tree-Style Array finished, continuing queries **********/
    /*****/ struct q_data {
    /*****/     int v, pos;
    /*****/     q_data* next;
    /*****/ } table[maxn], *head[maxn];
    /*****/ int q_tot;
    /*****/ void add_q_data(int x, int y, int z)
    /*****/ {
    /*****/     q_data *p = &table[++q_tot];
    /*****/     p->v = y; p->pos = z;
    /*****/     p->next = head[x]; head[x] = p;
    /*****/     return ;
    /*****/ }
    /********** End of query manager **********/
    int res[maxn];
    void solve(int n, char str[])
    {
        stack<node*> stk;
        stk.push(root);
        for (int j = 1; j <= n; j++) {
            if (str[j] == 'B') {
                change(stk.top()->dfn, -1);
                stk.pop();
            } else if (str[j] == 'P') {
                for (q_data *i = head[stk.top()->end]; i; i = i->next)
                    res[i->pos] = query(end[i->v]) - query(start[i->v] - 1);
            } else {
                stk.push(stk.top()->ch[str[j] - 'a']);
                change(stk.top()->dfn, 1);
            }
        }
        return ;
    }
} ac;

int n, m;
char str[maxn];

int main(int argc, char** argv)
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    ac.build_tree(n, str);
    ac.dfs(ac.root);
    scanf("%d", &m);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        ac.add_q_data(y, x, i);
    }
    ac.solve(n, str);
    for (int i = 1; i <= m; i++)
        printf("%d\n", ac.res[i]);
    return 0;
}