USACO Bronze 2015 February - Censoring

Official Analysis (C++)

Explanation

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

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

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

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

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

Implementation

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

Copy
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

Copy
#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;

Copy
import java.io.*;
import java.util.*;

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

Video Solution

By Amogha Pokkulandra