(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 far too slow. Each call to find alone takes $O(TS)$ time (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 for small strings T.
To fix this problem consider building the result string, $R$, one character at a time. Whenever the end of $R$ matches $T$ we should delete it from $R$. Since this deletion is at the end of $R$ this is just a simple $O(1)$ resize operation.
Now the main problem is how to determine if the end of $R$ matches $T$ efficiently. I will discuss two ways of accomplishing this.
In summary, we can initially compute the hash of $T$, $H(T)$, and additionally compute a rolling hash of the end of $R$. It's ok (and preferable) to do a full string comparison in case the hashes match to ensure that the strings really do match. Since they do with high probability we can amortize this against the length of $R$ that we'll delete.
Using a polynomial hash we can keep track of the hash of every prefix of $R$ which can be used to quickly reconstruct the hash of the last $|T|$ characters of $R$ making the overall runtime of the algorithm $O(S)$ in expectation.
Here's my hashing-based solution to this problem:
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; #define HM 1000000007 #define HA 100000007 #define HB 101 /* Given the hash 'h' of string S, computes the hash of S + 'ch'. */ int hext(int h, int ch) { return (1ll * h * HA + ch + HB) % HM; } int main() { freopen("censor.in", "r", stdin); freopen("censor.out", "w", stdout); /* Read the input strings. */ string S, T; cin >> S >> T; /* Compute the hash of T. */ int thsh = 0; for (int i = 0; i < T.size(); i++) { thsh = hext(thsh, T[i] - 'a'); } /* Build the result string one character a time. */ string R; vector<int> rhsh(1, 0); vector<int> HAPW(1, 1); for (int i = 0; i < S.size(); i++) { /* Update the result string. */ R += S[i]; /* Calculate the hash of the new result string. */ rhsh.push_back(hext(rhsh.back(), S[i] - 'a')); /* Calculate the next power of HA. */ HAPW.push_back((1ll * HAPW.back() * HA) % HM); if (R.size() >= T.size()) { /* Compute the hash of the last |T| characters of R. This is done by subtracting out * the prefix before the last T characters from the entire hash of R (multiplying by the * appropriate power of HA). */ int hsub = (1ll * rhsh[R.size() - T.size()] * HAPW[T.size()]) % HM; int hsh = (HM + rhsh.back() - hsub) % HM; /* If the end of R and T match truncate the end of R (and associated hash arrays). */ if (hsh == thsh && R.substr(R.size() - T.size()) == T) { R.resize(R.size() - T.size()); rhsh.resize(rhsh.size() - T.size()); HAPW.resize(HAPW.size() - T.size()); } } } cout << R << endl; return 0; }