← CSES Better

Censoring (Gold)

USACO · 2015 · February · gold-2

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

strings · aho-corasick

The organizer’s problem statement is available at the official source link.

sample trace

Censoring: remove any matching pattern

The sample has two forbidden words. An automaton tracks all pattern prefixes while characters are appended; when one completes at the stack suffix, remove it and restore the previous match state.

input

begintheescapexecutionatthebreakofdawn

patterns

escapeexecution

removed In Order

escapeexecution

output

beginthatthebreakofdawn

trace

begintheescapexecutionatthebreakofdawnbegintheexecutionatthebreakofdawnbeginthatthebreakofdawn
  1. 1

    Build multi-pattern matcher

    Insert escape and execution into a trie and add failure links so suffix matches are found in one pass.
  2. 2

    Append and match

    Scan the input into an output stack while tracking the automaton state for each stack prefix.
  3. 3

    Pop completed words

    Remove a completed forbidden suffix immediately; the sample removes escape, then execution.
  4. 4

    Finish

    The remaining text is beginthatthebreakofdawn, matching the published output.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.