[USACO15FEB] Censoring G

GitHub跳转原题关系图返回列表

用 AC 自动机在线识别多个敏感词后缀，并用字符栈和状态栈完成删除后的状态回退。

OJ: luogu

题目 ID: P3121

难度:提高+/省选-

标签:字符串AC自动机栈模拟

日期: 2026-06-22 22:24

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定一个原字符串和若干敏感词。每次删除当前字符串中开始位置最早的敏感词，删除后左右拼接，继续重复，直到没有敏感词。

输出最终剩下的字符串。

思路

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：每次查找最早出现的敏感词并删除，只适合小数据。

string s;
int n;
vector<string> words;

void solve_brute() {
    while (true) {
        int best_pos = -1;
        int best_id = -1;

        for (int i = 0; i < n; i++) {
            size_t pos_value = s.find(words[i]);
            if (pos_value == string::npos) {
                continue;
            }
            int pos = (int)pos_value;
            if (best_pos == -1 || pos < best_pos) {
                best_pos = pos;
                best_id = i;
            }
        }

        if (best_pos == -1) {
            break;
        }
        s.erase(best_pos, words[best_id].size());
    }
}

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

    cin >> s;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string t;
        cin >> t;
        words.push_back(t);
    }

    solve_brute();
    cout << s << '\n';

    return 0;
}

暴力每轮重新查找最早出现的敏感词，符合题意但效率太低。

考虑从左到右扫描原串，并维护“当前还没被删除的结果串”。每读入一个字符，就把它压入结果栈。此时如果结果栈的后缀刚好是某个敏感词，就立刻弹出这个敏感词长度的字符。

多个敏感词需要快速判断“当前后缀是否匹配”，所以使用 AC 自动机。

还需要解决删除后的状态回退：每个栈位置保存当前结果串对应的 AC 状态。

流程如下：

  1. 把所有敏感词插入 AC 自动机；
  2. 建失败指针和完整转移；
  3. 扫描原串：
    • 字符入栈；
    • 从上一个状态转移到新状态；
    • 保存新栈顶状态；
    • 如果当前状态匹配某个敏感词，就弹出对应长度。
  4. 输出栈中剩余字符。

弹出后，新的栈顶保存着删除后的 AC 状态，所以后续字符可以继续正确处理跨删除边界形成的新敏感词。

代码

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

const int MAXLEN = 200005;
const int ALPHA = 26;

int trie[MAXLEN][ALPHA];
int fail_link[MAXLEN];
int word_len[MAXLEN]; // 若当前状态结尾匹配某个单词，记录这个单词长度。
int node_cnt;

string s;
int n;
string word;
char answer_stack[MAXLEN];
int state_stack[MAXLEN];
int top_pos;

void insert_word(const string &text) {
    int p = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        int c = text[i] - 'a';
        if (trie[p][c] == 0) {
            node_cnt++;
            trie[p][c] = node_cnt;
        }
        p = trie[p][c];
    }
    word_len[p] = (int)text.size();
}

void build_ac() {
    queue<int> que;
    for (int c = 0; c < ALPHA; c++) {
        int v = trie[0][c];
        if (v != 0) {
            que.push(v);
        }
    }

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int c = 0; c < ALPHA; c++) {
            int v = trie[u][c];
            if (v != 0) {
                fail_link[v] = trie[fail_link[u]][c];
                que.push(v);
            } else {
                trie[u][c] = trie[fail_link[u]][c];
            }
        }

        // 题目保证单词互不为子串，正常不会需要继承；保留可增强健壮性。
        if (word_len[u] == 0 && word_len[fail_link[u]] != 0) {
            word_len[u] = word_len[fail_link[u]];
        }
    }
}

void read_input() {
    cin >> s;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> word;
        insert_word(word);
    }
}

void solve() {
    build_ac();

    top_pos = 0;
    state_stack[0] = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        int c = s[i] - 'a';
        int next_state = trie[state_stack[top_pos]][c];

        top_pos++;
        answer_stack[top_pos] = s[i];
        state_stack[top_pos] = next_state;

        if (word_len[next_state] > 0) {
            top_pos -= word_len[next_state];
        }
    }

    for (int i = 1; i <= top_pos; i++) {
        cout << answer_stack[i];
    }
    cout << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

设原串长度为 S，敏感词总长度为 T。

时间复杂度为 O(26T+S)O(26T + S)，空间复杂度为 O(S+T)O(S+T)。

总结

这道题的关键不是只会 AC 自动机，而是把自动机状态和栈绑定在一起。

字符被删除时，状态也要一起回退；保存每个栈位置的状态，就能让删除操作保持 O(1)O(1)。