Censoring

알고리즘 구분 : 문자열

문제

Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).

FJ has taken all of the text from the magazine to create the string S of length at most 10^6 characters. From this, he would like to remove occurrences of a substring T of length <= 100 characters to censor the inappropriate content. To do this, Farmer John finds the first occurrence of T in S and deletes it. He then repeats the process again, deleting the first occurrence of T again, continuing until there are no more occurrences of T in S. Note that the deletion of one occurrence might create a new occurrence of T that didn't exist before.

Please help FJ determine the final contents of S after censoring is complete.

입력
The first line will contain S. The second line will contain T. The length of T will be at most that of S, and all characters of S and T will be lower-case alphabet characters (in the range a..z).

출력
The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.

예제 입력 1
whatthemomooofun
moo
예제 출력 1
whatthefun

문제 풀이

결과문자열을 만들어가는 과정에서 예제를 보면 알 수 있겠지만, 비교를 할 때, 시작지점을 잡아서 비교하게 된다면 반복문을 통한 확인은 구현이 어렵다. whatthemomooofun에서 moo를 찾을 때, 첫 번째 moo를 찾아서 삭제하는 과정은 쉬울 수 있지만, 두 번째 moo를 찾는 과정은 다시 처음부터 시작 idx에서 비교를 하는 시간 복잡도가 높아지는 방식을 추구할 수 밖에 없다. 그렇기에, 문자열이 매우 길 경우, 이는 TLE를 발생시킬 수 있기에, 한 번 탐색하면서 이를 비교할 수 있도록 해야 한다.
그렇기에, 삭제해야할 문자열의 크기만큼, 현재까지의 result 문자열에서 substr함수를 활용해 문자열을 부분추출하여, 비교하여 동일할 경우, resize함수를 통해 뒤 부분을 날리는 방식을 할 수 있도록 구현하였다.

string 클래스 사용 함수 설명
string::substr(시작인덱스, 문자열길이)
1. 아무것도 입력하지 않을 경우, 문자열 전체를 추출
2. 시작인덱스만 입력시, 시작 인덱스부터 문자열 끝까지를 추출
3. 시작인덱스와 문자열길이를 입력시, 시작인덱스부터 지정된 길이만큼의 문자열을 추출

string::resize(크기, 남은 공간을 채울 문자)
1. 입력된 크기만큼으로 string 변수의 크기를 조정함.
2. 만약 그 크기가 원래 사이즈보다 작다면, 남은 스트링을 버립니다.
3. 만약 그 크기가 원래 사이즈보다 크다면, 빈 공간으로 남은 공간을 채움
4. 남은 공간을 채울 문자를 두 번째 변수로 넣는다면, 남은 공간을 해당 문자로 채움

소스 코드

#include <bits/stdc++.h>

using namespace std;

string s, t, result;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> s >> t;
	
	solve();
	
	return 0;
}

void solve() {
	for(int i = 0; i < s.size(); i++) {
		result += s[i];
		
		if(result.size() >= t.size() && result.substr(result.size() - t.size()) == t) {
			result.resize(result.size() - t.size());
		}
	}
	
	cout << result << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/10750
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.