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

以上就是關(guān)于【USACO 2015 February Contest, Bronze Problem 1. Censoring (Bronze)】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動(dòng)：留學(xué)申請(qǐng)的“核武器”來(lái)了！

2026理工科競(jìng)賽“大洗牌”：線上考試終結(jié)、報(bào)名門(mén)檻收緊、晉級(jí)規(guī)則重塑...你準(zhǔn)備好了嗎？