글 읽기 - 문자열 폭발 시간초과 질문입니다.

cubalys 8년 전 0

입력받은 문자열 앞에서 부터 하나씩 Stack에 쌓다가

방금 쌓은 문자가 폭탄 문자열의 맨 마지막 문자와 일치하면

폭탄 문자열의 사이즈 만큼 앞으로 검사하여

정확히 일치하는 경우 폭탄 문자열의 사이즈 만큼 팝을 시켜주는 방식으로 작성했습니다.

제가 동작시킨 몇가지 예제도 제대로 동작하고

시간같은 경우에도

최대 100만 * 36 = 3600만

인데 왜 시간초과가 나는지 모르겠네요..

딱히 무한루프를 돌만 한 구간도 없는거 같은데...

#include <iostream>
#include <string.h>
using namespace std;
char Text[1000001], Bomb[37], Stack[1000001], Bomb_Last;
int Point, Bomb_Size;
int main() {
	cin >> Text >> Bomb;
	Bomb_Size = strlen(Bomb);
	Bomb_Last = Bomb[Bomb_Size-1];
	for (int i = 0; i < strlen(Text); i++) {
		Stack[Point++] = Text[i];
		if (Point >= Bomb_Size && Text[i] == Bomb_Last) {
			int j, k;
			for (j = Point-1, k = Bomb_Size - 1; k >= 0; j--, k--) 
				if (Stack[j] != Bomb[k]) break;
			if (k == -1) Point -= Bomb_Size;
		}
	}
	if (Point == 0) cout << "FRULA" << endl;
	else {
		for (int i = 0; i < Point; i++)
			cout << Stack[i];
		cout << endl;
	}
}