USACO Bronze 2015 February - Censoring

Authors: Brad Ma, Ahmad Bilal

Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

Let us define censored\texttt{censored} as the final censored text.

We can iterate through every character of ss, appending it to censored\texttt{censored}. However, whenever we append a character we we need to check if censored\texttt{censored} ends with the censored word. If it does, we remove it from censored\texttt{censored} by taking off the last few characters.

As a demonstration, let's try this on the example case where:

s=whatthemomooofunt=moos=\texttt{whatthemomooofun} \newline t=\texttt{moo}

Our solution will loop through each character of ss, appending it to censored\texttt{censored} until it becomes whatthemomoo\texttt{whatthemomoo}, when it will cut off the last 3 characters since they equal tt. This results in censored\texttt{censored} becoming whatthemo\texttt{whatthemo}.
Right after this, censored\texttt{censored} becomes whatthemoo\texttt{whatthemoo} as the next letter in ss is oo, so we omit the last 3 characters again and censored\texttt{censored} becomes whatthe\texttt{whatthe}.

After this, the check isn't triggered anymore, so we end up with whatthefun\texttt{whatthefun} as our final word.

Implementation

Time Complexity: O(ST)\mathcal{O}(S \cdot T)

Python

import sys
sys.stdin = open('censor.in', 'r')
sys.stdout = open('censor.out', 'w')
s = input().strip()
t = input().strip()
censored = ""
# Add each character to the censored string
for char in s:

C++

#include "bits/stdc++.h"
using namespace std;
Code Snippet: {USACO-style I/O. See General / Input & Output (Click to expand)
int main() {
setIO("censor");
string s;
string t;
cin >> s >> t;

Java

import java.util.*;
import java.io.*;
public class Censor {
public static void main (String[] args) throws IOException {
Kattio io = new Kattio("censor");
String s = io.next();
String t = io.next();
// We use StringBuilder in Java because it's significantly faster

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!