백준 9935 문자열 폭발

백준 9935
이 문제는 n이 최대 백만개 이기 때문에 그냥 탐색을 통해서 풀면 시간초과가 발생한다. O(n)으로 풀리는 방법이 있다.
s : 처음 문자열 , s1 : 폭발 문자열
1. s 문자열을 처음부터 탐색하면서 s1 문자열의 마지막 인덱스의 문자와 같은 것을 탐색
2. 존재시 뒤에서부터 s1 문자열과 완전히 같은지 탐색
2.1 폭발 문자열 탐색 성공시 s에서 폭발 문자열을 지우고 (idx 수정)
2.2 폭발 문자열 탐색 실패시 idx+1 증가
3. 1,2를 s 문자열 끝까지 반복

ex) 
mirkovC4nizCC44
C4

s: mirkovC4nizCC44, s1: C4

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14			
m i r k o v C 4 n i z  C  C  4  4  
-> 폭발 문자열 탐색 성공 -> idx=7-2+1=6 
-> s[6] = s[8]
-> 0 1 2 3 4 5 6 7 8 9 10 11 12
   m i r k o v n i z C C  4  4
   
이걸 반복!

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	string s, s1;
	cin >> s >> s1;

	int idx = 0;
	for (int i = 0; i < s.size(); i++) {

		s[idx] = s[i];

		int flag = 1;
		if (s[idx] == s1[s1.size() - 1]) { //폭발 문자열 탐색
			int k = 1;
			for (int j = s1.size() - 2; j >= 0; j--) {
				if (s[idx - k] != s1[j]) { //폭발 문자열 탐색 실패
					flag = 0;
					break;
				}
				k++;
			}
			if (flag) { //폭발 문자열 탐색 성공
				idx = idx - k + 1;
			}
			else { //폭발 문자열 탐색 실패
				idx++;
			}
		}
		else idx++;
	}
	if (idx <= 0) cout << "FRULA" << '\n';
	else {
		for (int i = 0; i < idx; i++) cout << s[i];
	}
}