Censoring

Explicación

Definamos $\texttt{censored}$ como el texto final censurado.

Podemos iterar sobre cada carácter de $s$ , agregándolo a $\texttt{censored}$ . Sin embargo, cada vez que agregamos un carácter hay que revisar si $\texttt{censored}$ termina con la palabra a censurar. Si es así, la quitamos de $\texttt{censored}$ eliminando los últimos caracteres.

Como demostración, probemos esto en el caso de ejemplo donde:

\begin{align*} s&=\texttt{whatthemomooofun} \\ t&=\texttt{moo} \end{align*}

Nuestra solución recorre cada carácter de $s$ , agregándolo a $\texttt{censored}$ hasta que se convierte en $\texttt{whatthemomoo}$ , momento en el que corta los últimos 3 caracteres porque son iguales a $t$ . Esto hace que $\texttt{censored}$ pase a ser $\texttt{whatthemo}$ . Justo después, $\texttt{censored}$ se convierte en $\texttt{whatthemoo}$ porque la siguiente letra de $s$ es $o$ , así que omitimos de nuevo los últimos 3 caracteres y $\texttt{censored}$ queda $\texttt{whatthe}$ .

Después de esto, la comprobación ya no se activa, así que terminamos con $\texttt{whatthefun}$ como palabra final.

Implementación

Complejidad temporal: $\mathcal{O}(S \cdot T)$

PythonC++Java


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:
	censored += char
	# If the end of the string is t, we remove t from the end
	if censored[-len(t) :] == t:
		censored = censored[: -len(t)]
 
print(censored)


#include "bits/stdc++.h"
using namespace std;
 
// BeginCodeSnip{{USACO-style I/O. See General / Input & Output}}
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if ((int)name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
// EndCodeSnip
 
int main() {
	setIO("censor");
	string s;
	string t;
	cin >> s >> t;
 
	string censored;
	// Add each character to the censored string
	for (int i = 0; i < s.size(); i++) {
		censored += s[i];
		// If the end of the string is t, we remove t from the end
		if (censored.size() >= t.size() &&
		    censored.substr(censored.size() - t.size()) == t) {
			censored.resize(censored.size() - t.size());
		}
	}
	cout << censored << endl;
}


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
		StringBuilder censored = new StringBuilder();
		censored.append(s.substring(0, t.length() - 1));
 
		// Add each character to the censored string
		for (int x = t.length() - 1; x < s.length(); x++) {
			censored = censored.append(s.charAt(x));
			// We need to check if our current string's longer than the censored
			// word
			if (censored.length() >= t.length()) {
				String check = censored.substring(censored.length() - t.length());
				// If the end of the string is t, we remove t from the end
				if (check.equals(t)) {
					censored.delete(censored.length() - t.length(), censored.length());
				}
			}
		}
		io.println(censored);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Solución en video

Por Amogha Pokkulandra

Video de YouTube (ag46IZcJRQk)

Código de la solución en video

C++Java


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	freopen("censor.in", "r", stdin);
	freopen("censor.out", "w", stdout);
 
	string S, T;  // String S and T, what we want to censor and the censor word
	cin >> S >> T;
	string out = "";  // No need for StringBuilder because c++ strings are mutable
 
	for (int i = 0; i < S.length(); i++) {
		// Reading in characters one at a time
		out += S[i];
 
		// Checking length condition
		if ((out.length() >= T.length()) &&
		    out.substr(out.length() - T.length()) == (T)) {
			// Resizing the string such that it does not contain censor word
			out.resize(out.size() - T.size());
		}
	}
 
	cout << out;
}


import java.io.*;
 
public class Censoring {
	public static void main(String[] args) throws IOException {
		// file in and out
		PrintWriter = pw = new PrintWriter(new File("censor.out"));
		BufferedReader br = new BufferedReader(new FileReader(new File("censor.in")));
 
		// String S, what we want to censor
		String S = br.readLine();
		// String T, the censored word
		String T = br.readLine();
		// StringBuilder solves the problem of immutable strings, so less memory
		// is taken up
		StringBuilder out = new StringBuilder("");
 
		for (int i = 0; i < S.length(); i++) {
			// Adding each character to the result one at a time
			out.append(S.substring(i, i + 1));
 
			// Checking the length of the result and whether the censor word
			// exists
			if ((out.length() >= T.length()) &&
			    out.substring(out.length() - T.length()).contentEquals(T)) {
				// Deleting the censored word, should it exist
				out.delete(out.length() - T.length(), out.length());
			}
		}
 
		System.out.println(out.toString());
		pw.println(out);
		pw.close();
		br.close();
	}
}