# USACO Bronze 2015 February - Censoring

### Prerequisites

ExplanationImplementation

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:

$s=\texttt{whatthemomooofun} \newline t=\texttt{moo}$

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)$

Python

import syssys.stdin = open('censor.in', 'r')sys.stdout = open('censor.out', 'w')
s = input().strip()t = input().strip()
censored = ""# Add each character to the censored stringfor 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!