黑暗爆炸 2434. 阿狸的打字机

发表于 更新于 分类于

链接

https://darkbzoj.tk/problem/2434

题意

给出一个只有小写字母，B 和 P 的字符串。

在输入区：

  • 对于小写字母，打印；
  • 对于 B，删去一个小写字母；
  • 对于 P，记录下当前输入区的字符串。

我们会得到很多个字符串。

有 $m$ 个询问，求第 $x$ 个字符串在第 $y$ 个字符串中出现了多少次。

思路

建立 AC 自动机和 fail 树。

fail 树上每个节点代表的字符串都是该节点子树节点代表的字符串的后缀。

因此对于每次询问第 $x$ 个字符串在第 $y$ 个字符串中出现的次数，我们只需要求第 $y$ 个字符串的前缀在第 $x$ 个字符串的子树中的个数。

我们可以用 DFS 序 + 树状数组维护。

我们可以离线查询，记录对于 $y$ 的询问。

在遍历主串时：

  • 遇到 B，对当前点 $-1$ 后回退；
  • 遇到 P，查询；
  • 否则，对当前点 $+1$。

时间复杂度：$O(n\log(n))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e5+5;
string s;
int m,pre[N],id[N],res[N],tr[N][26],fail[N],sz[N],dfn[N],a[N],cnt,dfn_cnt;
VI g[N];
VPII q[N];
void insert() {
    int u=0,t=0;
    for(auto c:s) {
        if(c=='B') u=pre[u];
        else if(c=='P') id[++t]=u;
        else {
            if(!tr[u][c-'a']) tr[u][c-'a']=++cnt;
            pre[tr[u][c-'a']]=u;
            u=tr[u][c-'a'];
        }
    }
}
void build() {
    queue<int> q;
    for(int i=0;i<26;i++) if(tr[0][i]) g[0].PB(tr[0][i]),q.push(tr[0][i]);
    while(SZ(q)) {
        int u=q.front();
        q.pop();
        for(int v=0;v<26;v++) {
            if(tr[u][v]) {
                fail[tr[u][v]]=tr[fail[u]][v];
                g[tr[fail[u]][v]].PB(tr[u][v]);
                q.push(tr[u][v]);
            }
            else tr[u][v]=tr[fail[u]][v];
        }
    }
}
void dfs(int u) {
    dfn[u]=++dfn_cnt;
    sz[dfn[u]]=1;
    for(auto v:g[u]) {
        dfs(v);
        sz[dfn[u]]+=sz[dfn[v]];
    }
}
void update(int x,int v) {
    for(int i=x;i<=dfn_cnt;i+=i&-i) a[i]+=v;
}
int query(int l,int r) {
    int ret=0;
    for(int i=r;i;i-=i&-i) ret+=a[i];
    for(int i=l-1;i;i-=i&-i) ret-=a[i];
    return ret;
}
void solve() {
    int u=0;
    for(auto c:s) {
        if(c=='B') {
            if(u) update(dfn[u],-1);
            u=pre[u];
        }
        else if(c=='P') {
            for(auto x:q[u]) {
                res[x.SE]=query(dfn[x.FI],dfn[x.FI]+sz[dfn[x.FI]]-1);
            }
        }
        else {
            u=tr[u][c-'a'];
            if(u) update(dfn[u],1);
        }
    }
    for(int i=1;i<=m;i++) cout<<res[i]<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>s;
    insert();
    build();
    dfs(0);
    cin>>m;
    for(int i=1;i<=m;i++) {
        int x,y;cin>>x>>y;
        q[id[y]].EB(id[x],i);
    }
    solve();
    return 0;
}