2015 Feb Bronze Problem 1 Censoring (Bronze)

Official Problem Statement

Censoring (Bronze)

Problem

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

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

The output should be a single line containing the final version of S after all deletions have been made.

Solution

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

C++

#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

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

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