DDOSvoid's Blog

Luogu P5840 [COCI2015]Divljak

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P5840

简要题意：一开始现给定 $n$ 个字符串 $S_i$，同时有一个字符串集合 $P$，一开始是空的，接下来有 $m$ 次两种操作，第一种是向集合中添加一个字符串 $T$，第二种是查询 $S_k$ 是集合 $P$ 中多少串的子串

$n,m\le 10^5, \sum |S|+\sum|T|\le 2\times 10^6$

Solution

我们考虑对 $S$ 建立 $AC$ 自动机，每次新加入一个串 $T$，我们考虑它对于每个 $S$ 的贡献

显然 $T$ 的每个前缀的贡献都是 $fail$ 树上的一条到根的链，那么整个串 $T$ 的贡献就是这些链的并

求链的并有经典做法就是先将这些点按 $dfs$ 序排序，然后每个点加 $1$，$lca$​ 处减 $1$

时间复杂度 $O(L\log L)$​

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 2000010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

struct Edge {
    int to, next;
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

#define ch s[i] - 'a'
struct AC_automaton {
    int nxt[26], fail; 
} T[maxn]; int top = 1, rt = 1, id[maxn];
void insert(char *s, int k) {
    int now = rt, l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
        now = T[now].nxt[ch];
    } id[k] = now;
} 

void init_fail() { // Trie 图
    queue<int> Q;
    for (int i = 0; i < 26; ++i) {
        int &u = T[rt].nxt[i];
        if (!u) { u = rt; continue; }
        T[u].fail = rt; Q.push(u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); 
        for (int i = 0; i < 26; ++i) {
            int &v = T[u].nxt[i];
            if (!v) { v = T[T[u].fail].nxt[i]; continue; }
            T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
        }
    }
}

int Bit[maxn];
void add(int i, int v) { while (i <= top) Bit[i] += v, i += lowbit(i); }

int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s; 
}

int in[maxn], out[maxn], dep[maxn], f[maxn][21];
void dfs(int u) {
    static int cnt = 0;
    in[u] = ++cnt;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        dep[v] = dep[u] + 1; f[v][0] = u; dfs(v);
    } out[u] = cnt;
}

void init_lca(int n) {
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}

int get_lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; ~i; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; ~i; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
    
int n, m;
char s[maxn];

inline void solve_1() {
    cin >> s; int now = rt, l = strlen(s);
    vector<int> A; 
    for (int i = 0; i < l; ++i) {
        now = T[now].nxt[ch];
        A.push_back(now); 
    } sort(A.begin(), A.end(), [](const int &u, const int &v) { return in[u] < in[v]; });
    add(in[A[0]], 1); 
    for (int i = 1; i < A.size(); ++i)
        add(in[get_lca(A[i - 1], A[i])], -1), add(in[A[i]], 1); 
}

inline void solve_2() {
    int x; cin >> x; x = id[x];
    cout << get_sum(out[x]) - get_sum(in[x] - 1) << "\n";
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> s, insert(s, i); init_fail(); 
    for (int i = 1; i <= top; ++i) add_edge(T[i].fail, i);
    dep[1] = 1; dfs(1); init_lca(top); cin >> m;
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2();
    }
    return 0; 
}