#BOJ 9935文字列爆発

🎇文字列爆発
( https://www.acmicpc.net/problem/9935 )

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초 (추가 시간 없음)	128 MB	37090	8365	5733	22.975%

質問する
尚根は文字列に爆発文字列を埋め込んだ.文字列が爆発すると、文字列から消え、残りの文字列が結合されます.
爆発は次の手順で行われます.
文字列に爆発文字列が含まれている場合、すべての爆発文字列が爆発します.残りの文字列を順番に接続し、新しい文字列を形成します.
新しく生成された文字列には、爆発文字列が含まれる場合があります.
爆発は、爆発文字列が文字列に含まれないまで続いた.
尚根は爆発が終わった後に残った文字列をすべて求めてみた.時々残った文字がない.「FRULA」が出力されます.
爆発文字列には、2つ以上の同じ文字は含まれません.
入力
最初の行には文字列があります.文字列の長さは1以上で、1000000以下です.
2行目は爆発文字列を示します.長さは1以上36未満です.
どちらの文字列も小文字と大文字、数字0,1,...、9だけで構成されています.
しゅつりょく
最初の行は、爆発が終了した後に残ったすべての文字列を出力します.
入力例1
mirkovC4nizCC44
C4
サンプル出力1
mirkovniz
入力例2
12ab112ab2ab
12ab
サンプル出力2
FRULA
インプリメンテーション

/*
BOJ : https://www.acmicpc.net/problem/9935
backtracking 문자열 폭발
Versatile0010
*/

#include <bits/stdc++.h>
using namespace std;

string input;
string mine;
bool flag = false;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> input >> mine; // 문자열과 폭발 문자열 입력
	vector<char> str; // 입력 문자열을 저장할 vector
	const int input_size = (int)input.size(); // 문자열의 길이 백업
	const int mine_size = (int)mine.size(); // 폭발 문자열의 길이 백업
	for (int i = 0; i < input_size; i++) // 문자열 순환
	{
		str.push_back(input[i]); // 한글자씩 push
		if (str.size() >= mine_size) // str 에 저장된 문자가 폭발문자열보다 크면 탐색
		{
			flag = true; // 일단 flag 는 true 로 저장 ( 폭발문자열 포함하지 않다면 false로 바뀜 )
			for (int j = 0; j < mine_size; j++) // 폭발문자열의 길이만큼 반복
			{
				if (str[str.size() - mine_size + j] != mine[j]) // str 에 폭발문자열이 없다?
				{
					flag = false; // false
					break; // 탈출
				}
			}
			if (flag == true) // 위 반복문 이후에도 flag 가 true 이면 폭발문자열이 포함된 것
			{
				for (int k = 0; k < mine_size; k++) // 폭발문자열의 길이만큼
				{
					str.pop_back(); // 문자열 팝
				}//문자열 폭발
				flag = false; // 폭발했으니까 flag 는 다시 false 로 저장
			}
		}
	}//반복

	if (str.empty() == true) // str 이 비어있다면 폭발로 모조리 날아간 것
	{
		cout << "FRULA"; // 예외처리
	}
	else
	{
		for (int i = 0; i < str.size(); i++) // str 이 비어있지 않다면.
		{
			cout << str[i]; // 그대로 출력 
		}
	}

	return 0;
}