글 읽기 - 왜 틀린건가요??

kkw564 7년 전 0

반례가 궁금합니다.. 어디서 틀린지 알 수 없네요 ㅠㅠ

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <string>

using namespace std;

char tmp[1000001];

// 실패함수
int getPi(string p)
{
	int max = 0;
	int m = (int)p.size();
	int j = 0;

	vector<int> pi(m, 0);

	for (int i = 1; i< m; i++) {
		while (j > 0 && p[i] != p[j])
			j = pi[j - 1];
		if (p[i] == p[j])
		{
			pi[i] = ++j;
			if (pi[i] > max)
				max = pi[i];
		}
	}
	return max;
}

int main()
{
	int n;
	
	string str, p;
	
	while(1)
	{
		scanf("%s", tmp);

		str = tmp;

		// .인 경우 종료
		if (str.size() == 1 && str[0] == '.')
			return 0;

		// 실페 함수중 최대 크기를 가진 값을 ans에 저장
		int ans = getPi(str);

		// 출력 과정
		if (ans == 0)
			printf("1\n");
		else
			printf("%d\n", str.size() / (str.size() - ans));
	}
	
	return 0;
}

red1108 5년 전 6

이 문제는 실패함수의 최댓값이 중요한게 아니라

마지막 실패함수 값이 중요합니다.

이 문제에서 말하는 반복의 의미와,실패함수의 정의를 다시 한번 생각해 보면 알수 있습니다.

따라서 마지막 실패함수 값만 가지고 계산하셔야 합니다.

str.size() / (str.size() - ans) 여기서 ans값만 최대값이 아니라 마지막 실패함수 값으로바꾸면 맞을꺼에요...

아 반례는 abababc입니다

red1108 5년 전 5

실제로, 위에 말한대로 ans를 마지막 실패함수 값으로 하니

바로 맞네요...^^

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

문제

문제

출처

ICPC

왜 틀린건가요??

kkw564 7년 전 0

red1108 5년 전 6

red1108 5년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말