USACO 2015 February Contest, Bronze Problem 1. Censoring (Bronze)

原题下载

USACO2015FEB-B1

答案

(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 ST times, it follows this has the runtime O(S2)). Additionally each erase call takes O(S) time meaning we spend O(S2T) 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;
}