BZOJ2434【NOI2011】阿狸的打字机

Posted on 2017-08-15 Symbols count in article: 1.5k Reading time ≈ 6 mins.

Problem

阿狸的打字机

Description

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 $B$ 、 $P$ 两个字母。
经阿狸研究发现，这个打字机是这样工作的：

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

例如，阿狸输入 $aPaPBbP$ ，纸上被打印的字符如下：
$a$
$aa$
$ab$
我们把纸上打印出来的字符串从 $1$ 开始顺序编号，一直到 $n$ 。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 $(x,y)$ （其中 $1\le x,y\le 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

1
2
3

2
1
0

Hint

$1\le N\le 10^5$
$1\le M\le 10^5 输入总长\le 10^5$

标签：AC自动机 Fail树 树状数组

Solution

这道题的提示还是很明显的。
读完题目，很容易发现此题打字的部分就是在建一棵 $Trie$ 。
输入小写字母即在 $Trie$ 中添加一个子结点并向儿子结点走，输入‘ $B$ ’即退回到父结点，输入’ $P$ ‘即在当前结点打标记。
因而我们可以构建 $Trie$ 如下：

void init() {
    //我写Trie树的习惯：把根节点定为1
    cnt = 0, root = 1, fa[root] = 0;
    //0号节点所有儿子都练到根，这样AC自动机CalcFail时更方便
    for (int i = 0; i < 26; i++)	trie[0][i] = root;
}
void build() {
    init();
    n = strlen(s);
    ind = 1;//ind记录当前结点数
    for (int i = 0, cur = root; i < n; i++) {
        if (s[i] == 'B') {
            //退到父结点
            cur = fa[cur];
        } else if (s[i] == 'P') {
            //打标记，标记为第cnt个字符串
            pos[++cnt] = cur;
        } else {
            //新建子结点
            trie[cur][s[i]-'a'] = ++ind;
            fa[ind] =cur, cur = ind;`
        }
    }
}

接下来我们对付这题的询问。
首先，它要求一个字符串在另一个字符串中出现多少次，这显然是 $AC$ 自动机的操作，所以我们建立 $fail$ 数组如下：

void CalcFail() {
    queue <int> que;
    que.push(root);
    while (!que.empty()) {
        int u = que.front();
        for (int i = 0; i < DICNUM; i++) {
            if (trie[u][i]) {
                fail[trie[u][i]] = trie[fail[u]][i];
                que.push(trie[u][i]);
            } else {
                trie[u][i] = trie[fail[u]][i];
            }
        }
        que.pop();
    }
}

现在我们考虑 $fail$ 数组的实质。如果 $A$ 结点的 $fail$ 指向 $B$ 结点，则 $B$ 结点代表的字符串一定是 $A$ 结点代表字符串的后缀，即经过 $A$ 的所有路径组成的字符串都包含 $B$ 结点代表的字符串。对于一个字符串，它的所有字串为它所有前缀的所有后缀，所以对于询问 $(x,y)$ ，我们需要找出从根节点到 $y$ 的路径中有多少结点可以通过 $fail$ 指针转移到 $x$ 。

这时我们就需要考虑 $Fail$ 树了。对于任意结点 $p$ ，我们把所有通过 $fail$ 指针能直接转移到 $p$ 的结点作为 $p$ 的子结点，而 $p$ 通过 $fail$ 指针转移到的结点作为 $p$ 的父结点。这样我们就能构建一棵树。这样一来，对于询问 $(x,y)$ ，问题等价于从根到 $y$ 的结点中有多少节点是在 $x$ 的子树中。我们就可以用 $DFS$ 序操作。然后用树状数组维护。

为了使询问变得更好操作，我们考虑把询问按 $y$ 值排序，这样我们就只需一直往下走，然后标记经过的结点，然后统计 $x$ 子树即可。

Code

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX_N 100000
#define DICNUM 26
using namespace std;
int n, m, cnt, ind;
int root, trie[MAX_N+5][DICNUM], fa[MAX_N+5], fail[MAX_N+5], pos[MAX_N+5], ans[MAX_N+5];
char s[MAX_N+5];
vector <int> G[MAX_N+5];
int into[MAX_N+5], outo[MAX_N+5];
int tr[MAX_N+5];
struct Query {int x, y, id;} q[MAX_N+5];
bool cmp (const Query &a, const Query &b) {return a.y < b.y;}
void init() {
    cnt = 0, root = 1, fa[root] = 0;
    for (int i = 0; i < DICNUM; i++)	trie[0][i] = root;
}
void CalcFail() {
    queue <int> que;
    que.push(root);
    while (!que.empty()) {
        int u = que.front();
        for (int i = 0; i < DICNUM; i++) {
            if (trie[u][i]) {
                fail[trie[u][i]] = trie[fail[u]][i];
                que.push(trie[u][i]);
            } else {
                trie[u][i] = trie[fail[u]][i];
            }
        }
        que.pop();
    }
}
void DFS(int u) {
    into[u] = ++ind;
    for (int i = 0; i < G[u].size(); i++)	DFS(G[u][i]);
    outo[u] = ind;
}
void build() {
    init();
    n = strlen(s);	ind = 1;
    for (int i = 0, cur = root; i < n; i++) {
        if (s[i] == 'B') {
            cur = fa[cur];
        } else if (s[i] == 'P') {
            pos[++cnt] = cur;
        } else {
            trie[cur][s[i]-'a'] = ++ind;
            fa[ind] = cur, cur = ind;
        }
    }
    CalcFail();
    for (int i = 1; i <= ind; i++)	G[fail[i]].push_back(i);
    ind = 0;
    DFS(root);
}
void inc(int pos) {for (; pos <= ind; pos += pos&(-pos))    tr[pos]++;}
void dec(int pos) {for (; pos <= ind; pos += pos&(-pos))    tr[pos]--;}
int sum(int pos) {int ret = 0; for (; pos; pos -= pos&(-pos))    ret += tr[pos]; return ret;}
void solve() {
    sort(q, q+m, cmp);
    for (int i = 0, j = 0, cur = root, now = 0; i < n; i++)
        if (s[i] == 'B') {
            dec(into[cur]);
            cur = fa[cur];
        } else if (s[i] == 'P') {
            now++;
            for (; j < m && q[j].y == now; j++)
                ans[q[j].id] = sum(outo[pos[q[j].x]])-sum(into[pos[q[j].x]]-1);
        } else {
            cur = trie[cur][s[i]-'a'];
            inc(into[cur]);
        }
}
int main() {
    scanf("%s", s);
    build();
    scanf("%d", &m);
    for (int i = 0; i < m; i++)	scanf("%d%d", &q[i].x, &q[i].y), q[i].id = i;
    solve();
    for (int i = 0; i < m; i++)	printf("%d\n", ans[i]);
    return 0;
}