백준 - 4354 문자열 제곱

본 문제의 요구사항은 다음과 같다.

임의의 두문자열의 곱은 두 문자열을 서로 이어 붙인 것으로 표현한다.

 

예를들면 "abcd" * "efg" = "abcdefg"

따라서 문자열의 제곱도 위와 같은 방식으로 표현할수 있다.

 

("abcd")² = "abcdabcd"

("aac")³ = "aacaacaac"

임의의 문자열(s) 이 주어졌을때 어떤 문자열 a에 대해서 s=aⁿ을 만족하는 가장 큰 n 을 구해야 한다.

 

본문제의 풀이과정은 아래와 같다.

a 의 길이는 s 의 길이의 약수이어야 한다. 따라서 s 의 약수길이에 해당되는 모든 sub 문자열이 동일한 값으로 반복되는지 검사를 하면 된다.

 

반복여부를 판단하기 위해서는 나머지 연산자를 적절히 이용하면 된다.

예를들어 s = "abcdabcdabcd" 라고했을때 s 가 abcd 의 반복인지 확인하는 방법은 다음과 같다.

s[0] , s[4] , s[8] 이 같은 값인지 검사

s[1] , s[5] , s[9] 가 같은 값인지 검사

s[2] , s[6] , s[10] 이 같은 값인지 검사

s[3] , s[7] , s[11] 이 같은 값인지 검사

 

0,4,8 은 각각 4로 나눈 나머지가 0 이다.

1,5,9 는 각각 4로 나눈 나머지가 1 이다.

2,6,10 은 각각 4로 나눈 나머지가 2이다.

3,7,11 은 각각 4로 나눈 나머지가 3이다.

 

임의의 s[k] 는 s[k % 4] 와 동일한지 체크를 해보고 모든 s[k] 가 s[k%4] 와 같은지 검사하면 된다.  

즉 4는 서브 문자열의 길이이다.

조건을 만족하는 가장 작은길이의 서브문자열 의 길이를  s 의 길이에서 나누어 주면 정답이 된다.

 

구현된 코드는 아래와 같다.

#include <iostream>
#include <string>

using namespace std;

void process(string &s)
{
	int result = 1;
	int szString = s.size();
	int curSz = szString;
	while (--curSz)
	{
		if (szString % curSz == 0)
		{
			int i;
			for (i = 0; i < szString; i++)
			{
				if (s[i] != s[i % curSz]) break;
			}
			if (i == szString)
			{
				result = szString / curSz;
			}
		}
	}
	cout << result << endl;
}

int main()
{
	string s;
	while (1)
	{
		cin >> s;
		if (s == ".") break;
		process(s);
	}
}