글 읽기 - c언어 4354 문자열 제곱 문제 반례를 부탁드립니다

sangchu8864 1년 전 0

문자열이 i길이의 부분문자열로 반복이 일어나면 실패함수에서

인덱스가 (i 의 배수-1)인 경우 그 값이 i만큼 계속 증가함을 이용하려고 했습니다.

ex) ABCABCABC의 경우(i=3) 실패함수가 0 0 0 1 2 3 4 5 6 이고 pi[2]=0 pi[5]=3 pi[8]=6

ABAABA(i=3) 의 경우 실패함수가 0 0 1 1 2 3 이기 때문에 pi[2]>=0 pi[5]=3

어디서 문제가 생기는지 잘 모르겠습니다ㅠㅠ

읽어주셔서 감사합니다!!

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char word[1000001]; //입력받을 문자열
int* p; //실패함수 저장
int len; //문자열 word의 길이

int* find(char *word) //실패함수 구하는 함수
{
	int* temp;
	
	temp = (int *)calloc(len, sizeof(int));
	int j = 0;
	for (int i = 1; i < len; i++)
	{
		while (j > 0 && word[i] != word[j])
		{
			j = temp[j - 1];
		}
		if (word[i] == word[j])
		{
			temp[i] = ++j;
		}
	}
	return temp;
}

int main(void)
{
	while (1)
	{
		gets_s(word);
		len = strlen(word);
		if (!strcmp(word, ".")) //.이 들어오면 종료
			return 0;
		
		free(p);
		p = find(word);


		int max = 1; //만족하는 가장 큰 n
		//i길이의 부분문자열로 반복되는지 각각 확인
		for (int i = 1; i <= len; i++) 
		{
			//문자열 word가 i로 나누어 떨어지지 않으면 반복 불가능
			if (len % i != 0)
				continue;
			int j;
			//길이가 i인 부분문자열이 j번째에서도 여전히 반복되는지 확인
			for (j = 0; (j)*i < len; j++)
			{
				//반복이 되지 않는다면 break;
				// abaaba와 같은 반례를 위해 != 가아닌 <이용
				if (p[(j+1) * i-1] < j*i)
					break;
			}
			//문자열 끝까지 반복이 되었다면 문자열의 길이/i 번 반복되었음
			if (i * (j) == len)
			{
				max = len / i;
				break;//성립하면 가장 큰 max를 찾은 것
			}
		}
		printf("%d\n", max);
	}
	return 0;
}

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

문제

문제

출처

ICPC

c언어 4354 문자열 제곱 문제 반례를 부탁드립니다

sangchu8864 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말