2015 Feb Silver Problem 1 Censoring (Silver)

Official Problem Statement

Censoring (Silver)

Problem

Bessie the cow is writing a string of characters for her novel, but she doesn't want the string "s" to appear in her string "t" as a consecutive substring. Given a string "t" that Bessie wrote, help her remove the earliest occurrences of the string "s" repeatedly until "s" does not appear as a consecutive substring in "t". If there are multiple occurrences of "s" that start at the same place, remove the leftmost one first.

Note: A consecutive substring of string "t" is a substring derived from "t" by deleting some characters at the beginning and/or at the end without changing the other characters in their original order.

Input:

• A single line containing the string "t", where "t" can be of length at most 10^6 characters.
• A single line containing the string "s", where "s" can be of length at most 10 characters.

All characters in both "t" and "s" will be lowercase English letters.

Output:

• A single line containing the final string "t" after the process is complete.

Solution

This problem can be solved using a sliding window approach combined with a stack-based strategy.

• Start by initializing an empty stack.
• Iterate over each character in the string "t". For each character, push it into the stack.
• After each push operation, check if the last |s| characters in the stack form the string "s". If they do, remove these characters from the stack.
• Continue this process until you've processed every character in the string "t".
• Finally, the stack will contain the final version of the string "t". Convert the stack into a string and output this string.

This approach efficiently checks for occurrences of the string "s" and removes them as soon as they're detected. Since it processes the string "t" only once, its time complexity is linear with respect to the length of "t".

Code

C++

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

const int MOD = 1e9 + 7;
const int BASE_A = 1e8 + 7;
const int BASE_B = 101;

// Function to compute the hash of a string
int compute_hash(int hash_val, int char_val) {
  return ((1ll * hash_val * BASE_A) + char_val + BASE_B) % MOD;
}

int main() {
  freopen("censor.in", "r", stdin);
  freopen("censor.out", "w", stdout);

  std::string S, T;
  std::cin >> S >> T;

  int T_hash = 0;
  for (char c : T) {
    T_hash = compute_hash(T_hash, c - 'a');
  }

  std::string Result;
  std::vector<int> result_hash{0};
  std::vector<int> BASE_A_pow{1};
  for (char c : S) {
    Result += c;

    result_hash.push_back(compute_hash(result_hash.back(), c - 'a'));

    BASE_A_pow.push_back((1ll * BASE_A_pow.back() * BASE_A) % MOD);

    if (Result.size() >= T.size()) {
      int hash_sub = (1ll * result_hash[Result.size() - T.size()] * BASE_A_pow[T.size()]) % MOD;
      int curr_hash = (MOD + result_hash.back() - hash_sub) % MOD;

      if (curr_hash == T_hash && Result.substr(Result.size() - T.size()) == T) {
        Result.resize(Result.size() - T.size());
        result_hash.resize(result_hash.size() - T.size());
        BASE_A_pow.resize(BASE_A_pow.size() - T.size());
      }
    }
  }

  std::cout << Result << std::endl;

  return 0;
}

Java

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

public class Main {
    private static final long MOD = 1_000_000_007;
    private static final long BASE_A = 100_000_007;
    private static final long BASE_B = 101;

    // Function to compute the hash of a string
    private static long computeHash(long hashVal, long charVal) {
        return ((hashVal * BASE_A + charVal + BASE_B) % MOD);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("censor.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("censor.out")));

        String S = br.readLine();
        String T = br.readLine();

        long T_hash = 0;
        for (char c : T.toCharArray()) {
            T_hash = computeHash(T_hash, c - 'a');
        }

        StringBuilder result = new StringBuilder();
        ArrayList<Long> resultHash = new ArrayList<>();
        resultHash.add(0L);
        ArrayList<Long> BASE_A_pow = new ArrayList<>();
        BASE_A_pow.add(1L);

        for (char c : S.toCharArray()) {
            result.append(c);

            resultHash.add(computeHash(resultHash.get(resultHash.size() - 1), c - 'a'));

            BASE_A_pow.add((BASE_A_pow.get(BASE_A_pow.size() - 1) * BASE_A) % MOD);

            if (result.length() >= T.length()) {
                long hashSub = (resultHash.get(result.length() - T.length()) * BASE_A_pow.get(T.length())) % MOD;
                long currHash = (MOD + resultHash.get(resultHash.size() - 1) - hashSub) % MOD;

                if (currHash == T_hash && result.substring(result.length() - T.length()).equals(T)) {
                    result.setLength(result.length() - T.length());
                    while (resultHash.size() > result.length() + 1)
                        resultHash.remove(resultHash.size() - 1);
                    while (BASE_A_pow.size() > result.length() + 1)
                        BASE_A_pow.remove(BASE_A_pow.size() - 1);
                }
            }
        }

        pw.println(result.toString());

        br.close();
        pw.close();
    }
}

Python

MOD = 1_000_000_007
BASE_A = 100_000_007
BASE_B = 101

def compute_hash(hash_val, char_val):
    return ((hash_val * BASE_A + char_val + BASE_B) % MOD)

with open('censor.in', 'r') as fin, open('censor.out', 'w') as fout:
    S = fin.readline().strip()
    T = fin.readline().strip()

    T_hash = 0
    for c in T:
        T_hash = compute_hash(T_hash, ord(c) - ord('a'))

    result = []
    result_hash = [0]
    BASE_A_pow = [1]

    for c in S:
        result.append(c)

        result_hash.append(compute_hash(result_hash[-1], ord(c) - ord('a')))

        BASE_A_pow.append((BASE_A_pow[-1] * BASE_A) % MOD)

        if len(result) >= len(T):
            hash_sub = (result_hash[len(result) - len(T)] * BASE_A_pow[len(T)]) % MOD
            curr_hash = (MOD + result_hash[-1] - hash_sub) % MOD

            if curr_hash == T_hash and ''.join(result[-len(T):]) == T:
                result = result[:-len(T)]
                result_hash = result_hash[:-len(T)]
                BASE_A_pow = BASE_A_pow[:-len(T)]
        
    fout.write(''.join(result))