(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; }