[C++]백준 - 4354번 문제

4354번: 문자열 제곱 (acmicpc.net)

4354번: 문자열 제곱

 

4354번 : 문자열 제곱

---

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

 

입력

---

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

 

 

출력

---

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

 

 

---

 

생각해 볼 점

---

KMP 알고리즘 중 실패함수를 이용하는 문제입니다.

 

실패함수의 생성 원리를 생각해보면 문자열의 제곱 형태를 계산하기 용이합니다.

 

예시) ABABAB의 실패함수

Index	0	1	2	3	4	5
값	0	0	1	2	3	4

위 표와 같이 생성이 되었을 것입니다. 여기서

 

입력된 문자열 X = ABABAB

반복되는 문자열 Y = AB

제곱된 횟수 N = 3 

 

라고 정의하겠습니다.

 

X의 길이 - 마지막 Index의 값 = Y의 길이

 

(마지막 Index의 값 / Y의 길이) + 1 = 3

 

만약, 마지막 Index의 값이 Y의 길이로 나누어떨어지지 않는다면 그 문자열 X는 문자열 제곱의 형태가 아니므로

 

1을 출력하면 됩니다.

 

코드

---

#include <iostream>
using namespace std;
#pragma warning(disable : 4996)

int main()
{
	while (true)
	{
		char input[1000001];
		cin.getline(input, 1000001);
		
		//탈출 조건
		if (input[0] == '.' && input[1] == NULL) break;
		//공백을 받으면
		if (input[0] == NULL)
		{
			printf("0\n");
			continue;
		}

		int len = 0;
		for (; input[len] != NULL; len++) continue;
		int *Pi = new int[len];
		fill_n(Pi, len, 0);
		
		//Pi 배열 만들기
		for (int left = 0, right = 1; right < len; right++)
		{
			while (0 < left && input[left] != input[right]) left = Pi[left - 1];
			if (input[left] == input[right]) Pi[right] = ++left;
		}


		printf("%d\n", (len % (len - Pi[len - 1]) == 0 ? len / (len - Pi[len - 1]) : 1));
	}
	return 0;
}

 

그 외

---