백준9935 문자열 폭발 - C++

뿌요뿌요 같은 게임이다.

폭발 문자열이 폭발하면서 사라지면

나머지 스트링이 합쳐지면서 

새로운 문자가 완성되고

거기에 또 폭발 문자열이 있다면

또 폭발하면서 새로운 문자열이 만들어지는 식이다.

 

모든 폭발이 끝났을 때 어떤 문자열이 남는지 확인해보자.

 

간단하게 스트링 패키지를 이용해보자.

 

input을 입력 받고 한 번의 순회만으로 

연산을 마쳐보자.

 

1. input 이 폭발 문자열이 없다고 가정하고 result에 추가한다.

2. result에 문자가 쌓이고 나면 마지막 글자를 폭발 문자열의 마지막 글자와 비교하여

   폭발 가능성이 있는지를 빠르게 판단한다.

3. 폭발 가능성이 없다면 계속 input을 result에 추가한다.

4. 폭발 가능성이 있다면 폭발 문자열과 비교한 뒤 폭발한다면 

    result에 저장된 스트링을 폭발 문자열의 길이만큼 무시한다. idx-= findlen;

  => 지울필요 없이 덮어 씌울 것이므로 해당 위치에서 다시 input 을 받는다.

#include <stdio.h>
#include <string.h>


char input[1000001];
char find[38];
char result[1000001];

int main() {
	scanf("%s", input);
	scanf("%s", find);
	int idx = 0;
	int inputlen = strlen(input);
	int findlen = strlen(find);
	for (int i = 0; i < inputlen; i++) {
		result[idx++] = input[i];
		//마지막 단어가 겹칠 경우
		if (result[idx - 1] == find[findlen - 1]) {
			if (idx - findlen < 0) continue; //당연히 안됨
			int flag = 1;
			for (int j = 0; j < findlen; j++) {
				if (result[idx - j - 1] != find[findlen - j - 1]) {
					flag = 0;
					break;
				}
			}
			if (flag) {
				idx -= findlen;
			}
		}
	}
	result[idx] = 0;
	//idx==0이면 암것도없음
	if (!idx) printf("FRULA\n");
	else printf("%s\n", result);
}