Boj 4354) 문자열 제곱

문제

백준 4354

방법 1

설명

KMP 의 Failure Function 의 응용으로 풀 수 있다.

시간 복잡도

O(\(\mathrm{N}\))

코드

string T;
int failTB[1000001];

int main()
{
	while (1)
	{
		cin >> T;
		if (T[0] == '.') break;

		for (int i = 1, j = 0; i < T.size(); i++)
		{
			while (j > 0 && T[i] != T[j]) j = failTB[j-1];
			if (T[i] == T[j]) failTB[i] = ++j;
	        else failTB[i] = 0;
		}
	
		int last_fail = failTB[T.size() - 1];
		int base_length = (T.size() - last_fail);
		if(last_fail != 0 && last_fail % base_length==0)
			cout << T.size() / base_length << '\n';
		else cout << 1 << '\n';
	}
}

방법 2

설명

s = a^k 꼴이라고 한다면 k 는 len(s) 의 약수가 된다. 여기서 모든 약수의 경우에서 수행한다면 시간초과가 난다. 하지만 어떤 k1, k2 가 s = a^k 를 성립시킨다면 LCM(k1, k2) 역시 마찬가지라는 성질을 이용하면 최적화할 수 있다.

len(s) 를 소인수분해 하여 소수마다 테스트를 시행하고, 테스트에 성공했다면 그의 거듭제곱에 대해서도 테스트를 수행한다. 그리고 테스트에 통과한 소수의 거듭제곱들을 곱해주면 답이 된다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

int primes[1000001];

// in = a^times 가 가능한지 테스트하는 함수
bool Valid(int times, string& in)
{
	int size = in.size(), stride = size / times;
	for (int i = stride; i < size; i += stride)
		for (int o = 0; o < stride; o++)
			if (in[o] != in[i + o])
				return false;
	return true;
}

int main()
{
    //에라토스테네스의 체
	for (int i = 2; i <= 1000000; i++)
		if(!primes[i])
			for (int j = i<<1; j <= 1000000; j += i)
				primes[j] = true;

	while (1)
	{
		string in;
		cin >> in;
		if (in == ".") break;
	
		int size = in.size();
	    int ans = 1;
	    if(Valid(size, in)) ans = size;
	    else{
	        int range = sqrt(size)+1;
	        for (int i = 2; i <= range; i++) 
			    if (size % i == 0 && !primes[i])
			    {
			    	int mul = 1;
			    	while (size % (mul*i) == 0 && Valid(mul * i, in)) mul *= i;
			    	ans *= mul;
			    }
	    }
				
		cout << ans << '\n';
	}
}