2015 Feb Bronze Problem 1 Censoring (Bronze)
Official Problem Statement[edit]
Problem[edit]
In the problem titled 'Censoring (Bronze)' from the USACO 2015 February Contest, the farmer John is trying to write a book but there is a specific word, let's call it T, that he finds displeasing and wants to remove from his text.
John has already written a word S. Every time word T appears in S as a consecutive substring, John deletes it. This process continues until there are no occurrences of T in S.
You are to help John decide what the final version of S will be after all deletions are made.
Input[edit]
The input consists of two lines. The first line contains the initial word S (1 ≤ |S| ≤ 1,000,000), composed of lowercase letters, and the second line contains the displeasing word T (1 ≤ |T| ≤ 100), also composed of lowercase letters.
Output[edit]
The output should be a single line containing the final version of S after all deletions have been made.
Solution[edit]
The solution involves processing the string S from left to right, adding each character to a resultant string. After each character is added, the algorithm checks if the last |T| characters of the resultant string match T. If they do, the last |T| characters are removed.
This process is continued until all characters in S have been processed, and the remaining characters in the resultant string constitute the final version of S. This can be implemented efficiently using a data structure such as a list or a stack which supports efficient append and truncate operations.
Code[edit]
C++[edit]
#include <iostream> #include <string> #include <cstdio> using namespace std; int main() { // Redirect input and output freopen("censor.in", "r", stdin); freopen("censor.out", "w", stdout); // Read input strings string S, T; cin >> S >> T; // Initialize the result string string result; // Iterate over the input string, appending each character to the result string for (char ch : S) { result += ch; // If the end of the result string matches the target string, delete it if (result.size() >= T.size() && result.substr(result.size() - T.size()) == T) { result.resize(result.size() - T.size()); } } // Output the final result string cout << result << endl; return 0; }
Java[edit]
import java.io.*; import java.util.Scanner; public class Main { public static void main(String[] args) throws FileNotFoundException { // Redirect input and output File inputFile = new File("censor.in"); File outputFile = new File("censor.out"); Scanner scanner = new Scanner(inputFile); PrintWriter writer = new PrintWriter(outputFile); // Read input strings String S = scanner.next(); String T = scanner.next(); // Initialize the result StringBuilder StringBuilder result = new StringBuilder(); // Iterate over the input string, appending each character to the result string for (char ch : S.toCharArray()) { result.append(ch); // If the end of the result string matches the target string, delete it if (result.length() >= T.length() && result.substring(result.length() - T.length()).equals(T)) { result.setLength(result.length() - T.length()); } } // Output the final result string writer.println(result.toString()); // Close scanner and writer scanner.close(); writer.close(); } }
Python[edit]
def main(): # Open input and output files with open('censor.in', 'r') as fin, open('censor.out', 'w') as fout: # Read input strings S, T = fin.read().split() # Initialize the result string result = [] # Iterate over the input string, appending each character to the result string for ch in S: result.append(ch) # If the end of the result string matches the target string, delete it if ''.join(result[-len(T):]) == T: del result[-len(T):] # Output the final result string fout.write(''.join(result)) if __name__ == "__main__": main()