Home » 国际竞赛 » Details

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

Category: 国际竞赛, 计算机国际竞赛 Date: 2017年12月8日下午3:30

原题下载

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 (T S)$ (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 (T S)$ 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;
}

以上就是关于【USACO 2015 February Contest, Bronze Problem 1. Censoring (Bronze)】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！新赛季翰林助力直通IOAI全球总决赛！