「一本通 2.2 练习 4」Censoring

形式化题目

给定主串 $S$ （ $1 \leqslant |S| \leqslant 10^5$ ）和 $n$ 个屏蔽词 $t_1 \sim t_n$ （ $1 \leqslant \sum |t_i| \leqslant 10^5$ ，均为小写字母），保证任何 $t_i$ 都不是 $t_j$ （ $i \neq j$ ）的子串。反复执行：在当前串中查找屏蔽词的一次出现并删除它（"从头开始寻找"即删最左出现），直到串中不再含屏蔽词，输出最终的串（保证非空）。

由"互不为子串"得到两个关键推论：同一位置结尾的屏蔽词至多一个（否则短的成为长的后缀）；某次出现的开始位置唯一对应一个屏蔽词。

正解

思路

朴素做法与两个瓶颈。 按题面模拟：每次从头找最左出现的屏蔽词，删除后回到开头再找。单次查找是 $O(|S| + |t|)$ ，最多删除 $O(|S| / \min|t|)$ 次，最坏总代价约 $O(|S| \cdot \sum |t|)$ ，对 $10^5$ 规模必然超时。瓶颈有两个：一是每次查找都要重新扫整条串；二是删除后要"从头再找"。下面分别用两个经典工具消掉它们。

瓶颈一：把"从头找"变成"转移一步"——AC 自动机。 把所有屏蔽词插入 trie，BFS 求出 fail 指针并把缺边补全成 fail 转移（trie 图），之后每读一个字符只需 $O(1)$ 查一次转移表。自动机状态的含义是：当前串的最长后缀中，是某个屏蔽词前缀的最长者。当转移落点是某个屏蔽词的结尾节点时，恰好说明当前串的末尾出现了屏蔽词。

为什么只需检查末尾？设已读入前缀反复删除后的保留串为 $R$ （归纳保证它不含屏蔽词），再读入字符 $c$ 。若 $R \cdot c$ 中有屏蔽词出现，它必然以 $c$ 结尾——否则它完全落在 $R$ 内，与 $R$ 无屏蔽词矛盾。又因为同一位置结尾的屏蔽词至多一个，所以 $R \cdot c$ 中至多出现一次屏蔽词：要么安全，要么整段弹出后自然干净。于是"反复从头找"就等价于"逐字符读入、末尾命中即删"，这是一次扫描能做完的根本原因。

瓶颈二：把"从头再找"变成"恢复状态"——栈。 删除让串变短，但被删部分之前的字符从未变过，变的只是拼接处。因此用两个平行栈：kept 存保留的字符，states 存每个前缀对应的自动机节点（states[i] 是前缀 kept[:i] 的状态，states[0] 是根）。命中长度为 $L$ 的屏蔽词时，把两栈各弹出 $L$ 个元素，然后 cur = states[-1]——这正是"删除后的串"的自动机状态，拼接处的匹配由自动机自动接上。

下面的图展示样例中两个屏蔽词建成的自动机（实边是 trie 边，虚边是关键的 fail 边，橙色节点是词尾）：

flowchart LR
    R((root)) -->|e| A["e"]
    A -->|s| B[es]
    B -->|c| C[esc]
    C -->|a| D[esca]
    D -->|p| E[escap]
    E -->|e| F["escape<br/>end = 6"]
    A -->|x| G[ex]
    G -->|e| H[exe]
    H -->|c| I[exec]
    I -->|u| J[execu]
    J -->|t| K[execut]
    K -->|i| L[executi]
    L -->|o| M[executio]
    M -->|n| N["execution<br/>end = 9"]
    F -. fail .-> A
    H -. fail .-> A
    style F fill:#ffe0b2
    style N fill:#ffe0b2

两个词只共享根和节点 e。重点看两条 fail 边：escape 和 exe 的 fail 都指向节点 e——一个屏蔽词的后缀可以同时是另一个屏蔽词的前缀。这正是"删除后拼接处能产生新屏蔽词"的结构来源。

用样例 $S =$ begintheescapexecutionatthebreakofdawn 走一遍扫描，下表展示保留栈的四个阶段：

阶段	本段读入	末尾是否命中	命中后栈 `kept`	命中后状态 `cur`
1	`beginthe`	否	`beginthe`	节点 `e`
2	`escape`	是（`escape`， $L=6$ ）	`beginthe`（弹出 `escape`）	节点 `e`（取自栈顶记录）
3	`xecution`	是（`execution`， $L=9$ ）	`beginth`（弹出栈中的 `e` 与刚读的 `xecution`）	根
4	`atthebreakofdawn`	否	`beginthatthebreakofdawn`	—

阶段 3 是全题最微妙的一步：删除 escape 后状态恢复为节点 e（beginthe 的最长后缀是前缀的只有 e），而 e 恰好也是 execution 的前缀，于是继续读入 xecution 时沿 $ex \to exe \to \cdots \to execution$ 一路匹配，最终弹出的 $9$ 个字符 = 栈里残留的 e + 刚读入的 8 个字符。如果删除后恢复的状态差一个字符（比如回退成 beginth 的状态），后面的匹配就全错了——这也是本题实现时最容易写错的地方。

词尾长度的预处理。 建自动机时用 end[v] = end[v] or end[fail[v]] 把"以该节点结尾的屏蔽词长度"沿 fail 链传播，命中时才知道要弹几个字符。由于屏蔽词互不为子串，fail 链上至多一个词尾，or 就够了，无需比较取 max。命中时"先把当前字符入栈再统一弹出 $L$ 个"，可以顺便避开单字符屏蔽词时 del kept[-0:] 会清空整个列表的 Python 切片坑。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:44
# update_at: 2026-09-30 12:44

import sys
from collections import deque


def build_automaton(words: list[bytes]) -> tuple[list[list[int]], list[int]]:
    """对屏蔽词建 AC 自动机：返回转移表 ch 与 end（节点 i 结尾的屏蔽词长度）。"""
    ch: list[list[int]] = [[0] * 26]  # 先只有 trie 边，0 = 无边（也是根）
    end: list[int] = [0]
    for w in words:
        cur = 0
        for c in w:
            c -= 97  # 'a' 的字节值
            if not ch[cur][c]:
                ch[cur][c] = len(ch)
                ch.append([0] * 26)
                end.append(0)
            cur = ch[cur][c]
        end[cur] = len(w)  # 屏蔽词互不为子串 → 每个节点至多结尾一个词

    fail: list[int] = [0] * len(ch)
    queue = deque(v for v in ch[0] if v)  # 第一层的 fail 都是根，默认即 0
    while queue:
        u = queue.popleft()
        for c in range(26):
            v = ch[u][c]
            if v:  # 真·孩子：定 fail 并沿链继承"以多长屏蔽词结尾"
                fail[v] = ch[fail[u]][c]
                end[v] = end[v] or end[fail[v]]
                queue.append(v)
            else:  # 补全成 trie 图：缺边改指向 fail 的同边，扫描时免跳 fail
                ch[u][c] = ch[fail[u]][c]
    return ch, end


def censor(s: bytes, ch: list[list[int]], end: list[int]) -> bytes:
    """从头匹配、命中即删：栈里存保留字符与各自前缀对应的自动机状态。"""
    kept: list[int] = []  # 保留字符（字节值）
    states: list[int] = [0]  # states[i] = 前缀 kept[:i] 的状态，states[0] = 根
    cur = 0
    for c in s:
        cur = ch[cur][c - 97]  # trie 图上一步转移，自带 fail 语义
        kept.append(c)
        states.append(cur)
        if end[cur]:  # 栈顶拼出了屏蔽词：连当前字符一起整段弹出，状态回到删除前的位置
            length = end[cur]
            del kept[-length:]
            del states[-length:]
            cur = states[-1]
    return bytes(kept)


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    s = next(it)
    second = next(it)
    if second.isdigit():  # 题面格式：第二个 token 是屏蔽词个数 n
        n = int(second)
        words = [next(it) for _ in range(n)]
    else:  # USACO 原始数据：第二个 token 就是唯一的屏蔽词
        words = [second, *it]
    ch, end = build_automaton(words)
    sys.stdout.buffer.write(censor(s, ch, end))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:59
 * update_at: 2026-10-05 02:59
 */

// Censoring：屏蔽词建 AC 自动机，逐字符扫描，命中词尾就按长度整段弹出。
// 关键观察：屏蔽词互不为子串 => 删除只会发生在保留串末尾，
// 且同一结尾位置至多一个屏蔽词，所以一次从左到右扫描即可完成全部删除。

#include <bits/stdc++.h>
using namespace std;

const int MAXNODE = 100005; // 屏蔽词总长 <= 1e5，trie 节点数不超过总长 + 1
const int ALPHA = 26;

typedef long long ll;

int ch[MAXNODE][ALPHA]; // trie 图转移表：ch[u][c] = 读到字符 c 后到达的节点
int fail_[MAXNODE];     // fail 指针，指向当前节点最长真后缀对应的节点
int end_[MAXNODE];      // end_[v] > 0 表示节点 v 结尾的屏蔽词长度
int tot = 1;            // 节点计数，0 号是根，1 号留给第一个新节点

char s[MAXNODE];    // 主串 S
char buf[MAXNODE];  // 读入屏蔽词用的缓冲区
char kept[MAXNODE]; // 栈：保存删除后保留下来的字符
int sta[MAXNODE];   // 平行状态栈：sta[i] = 保留前 i 个字符时的自动机节点
int top = 0;        // 栈中字符个数（即当前保留串长度）
int cur = 0;        // 当前保留串对应的自动机节点

// 把一个屏蔽词插入 trie。
void insert_word(const char *w) {
    int u = 0;
    for (int i = 0; w[i] != '\0'; i++) {
        int c = w[i] - 'a';
        if (ch[u][c] == 0) {
            ch[u][c] = tot++;
        }
        u = ch[u][c];
    }
    end_[u] = strlen(w); // 屏蔽词互不为子串 => 每个节点至多结尾一个词
}

// BFS 建 fail 指针，同时把缺边补全成 fail 转移（trie 图），
// 并把词尾长度沿 fail 链传播到所有后缀节点上。
void build_automaton() {
    queue<int> q;
    for (int c = 0; c < ALPHA; c++) {
        if (ch[0][c] != 0) {
            fail_[ch[0][c]] = 0; // 第一层的 fail 都是根
            q.push(ch[0][c]);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int c = 0; c < ALPHA; c++) {
            int v = ch[u][c];
            if (v != 0) {
                // 真孩子：定 fail，并继承 fail 链上的词尾长度
                fail_[v] = ch[fail_[u]][c];
                end_[v] = max(end_[v], end_[fail_[v]]);
                q.push(v);
            }
            else {
                // 补全成 trie 图：缺边改指向 fail 的同边，扫描时免跳 fail
                ch[u][c] = ch[fail_[u]][c];
            }
        }
    }
}

// 逐字符扫描主串：命中屏蔽词就按词长整段弹出，状态恢复为栈顶记录值。
void solve() {
    sta[0] = 0; // 空串对应根节点
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) {
        cur = ch[cur][s[i] - 'a']; // trie 图上一步转移，自带 fail 语义
        top++;
        kept[top] = s[i];
        sta[top] = cur;
        if (end_[cur] != 0) {
            // 栈顶拼出了屏蔽词：连当前字符一起弹出 end_[cur] 个，
            // 状态回到删除后串的状态，拼接处的匹配由自动机自动接上
            top -= end_[cur];
            cur = sta[top];
        }
    }
    kept[top + 1] = '\0';
    cout << kept + 1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> (s + 1); // 主串从下标 1 开始存，与栈下标对应
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> (buf + 1);
        insert_word(buf + 1);
    }
    build_automaton();
    solve();

    return 0;
}

复杂度

时间 $O(26 \cdot \sum |t_i| + |S|)$ ：建自动机对每个节点扫 $26$ 个转移；扫描每字符 $O(1)$ 转移，且每个字符至多入栈一次、出栈一次（均摊），删除的总代价不额外增长。
空间 $O(26 \cdot \sum |t_i| + |S|)$ ：trie 图转移表约 $26 \times 10^5$ 个整数，加栈与 fail/end 数组，实测峰值约 $53$ MB。

总结

题面"删掉再从头找"看似要反复扫串，但由"屏蔽词互不为子串"推出"删除只发生在保留串末尾、同一结尾至多一个屏蔽词"，从而把整个过程压成一次从左到右的扫描。
AC 自动机负责 $O(1)$ 定位"末尾是否出现屏蔽词"，栈里的 states 负责 $O(1)$ 恢复删除后串的状态，两者配合把两个瓶颈都消掉，总复杂度 $O(26 \cdot \sum |t_i| + |S|)$ 。
实现要点：end 沿 fail 链用 or 传播；命中分支先入栈再统一弹出；兼容本题面的 $n$ 词格式与 USACO 原始数据的单词格式（真实测试数据是后者）。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6题意：S 中出现屏蔽词就删，删完"从头再找"
`- 关键观察：删除只发生在保留串末尾，同一结尾位置至多一个屏蔽词
   `- 模型：屏蔽词建 AC 自动机，栈平行保存字符与每个前缀的状态
      |- 末尾命中：按 end 长度整段弹出，状态恢复为栈顶记录值
      |           → 拼接处（beginth + execution）自动续接匹配
      `- 复杂度：建图 O(26·∑|t|)，扫描均摊 O(|S|)

先看每个节点代表的推理结论，再顺着分支检查"末尾命中"如何同时解决查找与删除后重找两个瓶颈。图中只保留正文已经证明过的关键关系，不替代正文中的样例推演和正确性说明。