(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);
/* Read input strings. */
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;
}