글 읽기 - 9935번 문자열 폭발. KMP써서 풀었는데 폭발해버리겠습니다.

gkfkagkfka12 5년 전 0

질문란에 있는 테스트 케이스도 다해보고 대회테스트 케이스도 해봤는데

도대체 어느 반례가 있는지를 모르겠습니다 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

char t[1000005], p[40];
int n, m, q, s, pi[40];
bool none, boom;

void prefix(int m)
{
	int k = -1;

	pi[0] = -1;

	for (int q = 1; q < m; q++) {
		while (k > -1 && p[k + 1] != p[q]) k = pi[k];
		if (p[k + 1] == p[q]) k++;
		pi[q] = k;
	}
}

int main(void)
{
	fgets(t, 1000004, stdin);
	fgets(p, 39, stdin);

	t[strlen(t) - 1] = '\0';
	p[strlen(p) - 1] = '\0';

	n = strlen(t);
	m = strlen(p);
	
	prefix(m);

	q = -1;
	s = -1;
	int i = 0;
	while(i<n) {
		if (t[i] == '!') {
			i++;
			continue;
		}
		while (q > -1 && p[q + 1] != t[i]) {
			q = pi[q];
			s = -1;
		}
		if (p[q + 1] == t[i]) {
			if (s==-1) s = i;
			q++;
		}
		if (q == m-1) {
			for (int j = s; j <= i; j++)
				t[j] = '!';
			boom = true;
			q = -1;
		}
		if (boom) {
			boom = false;
			i = s + m + 1 - m * m; s = -1;
			if (i < 0) i = 0;
		}
		else i++;
	}

	none = true;
	for (int i = 0; i < n; i++) {
		if (t[i] != '!') {
			none = false;
			printf("%c", t[i]);
		}
	}
	if (none) printf("FRULA");


	return 0;
}