(Analysis by Mark Gordon)

This problem asks us to repeatedly delete the first occurrence of the string $T$ from a larger string $S$ until $T$ no longer appears in $S$. The literal translation of this process looks something like this:

while S.find(T)
S.erase(S.find(T))


Unfortunately this algorithm is a bit too slow. Each call to find takes $O(TS)$ (assuming the underlying implementation uses basic string matching). Since the loop can repeat at most $\frac{S}{T}$ times, it follows this has the runtime $O(S^2)$. Additionally each erase call takes $O(S)$ time meaning we spend $O(\frac{S^2}{T})$ time doing erase calls which is also too slow.

There are a couple of ways to overcome this performance problem. Perhaps the simplest is to build the final string one character at a time; whenever the end of the string matches T simply delete the end. Deleting the end of a string is more efficient than the middle of the string because no data needs to be moved after it. Using simple string comparisons this algorithm has runtime $O(TS)$ which is fast enough to pass all test data.

Here's my solution to this problem:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

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

string S, T;
cin >> S >> T;

/* Build R, the result string, one character at a time. */
string R;
for (int i = 0; i < S.size(); i++) {
R += S[i];

/* If the end of R matches T then delete it. */
if (R.size() >= T.size() && R.substr(R.size() - T.size()) == T) {
R.resize(R.size() - T.size());
}
}

cout << R << endl;

return 0;
}