글 읽기 - kmp를 사용하여 풀다가 틀왜맞 상황이 되어 질문드립니다

skyde47 4년 전 0

18번줄부터 fail 값을 구하는 부분을 제가 착각하여 잘못작성하였는데 오히려 훨씬 나은 성능으로 작동 합니다...

정말 무슨 이유로 이런 결과가 나오는지 도저히 모르겠어서 질문드립니다.

알고리즘 고수님들 도와주십쇼!!

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
const int MOD = 1e7;

string S, W, P;
int fail[37], slen, wlen, plen;
vector<char> v;
bool chk;

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> S >> W;
	slen = S.size();
	wlen = W.size();
    /* 정답
	for (int i = 1, j = 0; i < wlen; i++) {
		while (j > 0 && S[i] != S[j])j = fail[j - 1];
		if (S[i] == S[j])fail[i] = ++j;
	}
    */
    /* 시간초과
	for (int i = 1, j = 0; i < wlen; i++) {
		while (j > 0 && W[i] != W[j])j = fail[j - 1];
		if (W[i] == W[j])fail[i] = ++j;
	}
    */
	for (int i = 0, j = 0; i < slen; i++) {
		v.push_back(S[i]);
		while (j > 0 && S[i] != W[j])j = fail[j - 1];
		if (S[i] == W[j]) {
			if (j == wlen - 1) {
				j = fail[j];
				for (int q = 0; q < wlen; q++)v.pop_back();
				chk = true;
			}
			else j++;
		}
	}
	if (!chk) {
		cout << S;
		return 0;
	}
	while (1) {
		P.clear();
		for (char c : v)P.push_back(c);
		v.clear();
		chk = false;
		plen = P.size();
		for (int i = 0, j = 0; i < plen; i++) {
			v.push_back(P[i]);
			while (j > 0 && P[i] != W[j])j = fail[j - 1];
			if (P[i] == W[j]) {
				if (j == wlen - 1) {
					j = fail[j];
					for (int q = 0; q < wlen; q++)v.pop_back();
					chk = true;
				}
				else j++;
			}
		}
		if (v.empty()) {
			cout << "FRULA";
			return 0;
		}
		if (!chk) {
			cout << P;
			return 0;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

kmp를 사용하여 풀다가 틀왜맞 상황이 되어 질문드립니다

skyde47 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말