글 읽기 - 1701번 질문입니다.

qwebnm7788 6년 전 0

주어진 문자열에서 한 문자씩 줄여가면서 failure function 을 구하는 과정에서

얻을 수 있는 값 중 최대값을 구하는 방식으로 접근했습니다.

88%정도에서 틀렸습니다 가 나오는데 어느 부분을 수정해야할지 잘 모르겠습니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	string source;
	cin >> source;
	int ret = 0;
	for (int i = 0; i < source.length(); ++i) {
		string target = source.substr(i, source.length() - i);
		int size = target.length();
		vector<int> pi(size, 0);
		for (int j = 1, matched = 0; j < size; ++j) {
			if (matched > 0 && target[j] != target[matched]) matched = pi[matched - 1];
			if (target[j] == target[matched]) pi[j] = ++matched;
		}
		for (int j = 0; j < size; ++j)
			ret = max(ret, pi[j]);
	}
	cout << ret;
	
}

ckdfuf2001 6년 전 1

if (matched > 0 && target[j] != target[matched]) matched = pi[matched - 1];

이부분 if문 대신 while로 고치면 잘됩니다.

while(matched > 0 && target[j] != target[matched]) matched = pi[matched - 1];

원래 코드에서는 아마 테스트 문자가 aaaaaaaafbaaaaaaaaf인 경우?

안될거 같은 느낌이 드네요

ckdfuf2001 6년 전 1

aaaaafbaaaaf는 반례가 아니네요..

반례는 못찾았지만 if 문 while로 고치면 동작합니다!

qwebnm7788 6년 전 0

감사합니다!

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

문제

문제

출처

ICPC

1701번 질문입니다.

qwebnm7788 6년 전 0

ckdfuf2001 6년 전 1

ckdfuf2001 6년 전 1

qwebnm7788 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말