백준 / 4354 문자열 제곱

www.acmicpc.net/problem/4354

4354번: 문자열 제곱

kmp 알고리즘 중 pi 배열을 이용하는 문제입니다. 

pi 배열은 접두사, 접미사가 같은 최대 길이를 저장하는 역할을 합니다. 

pi[len]는 문자열의 0~len까지의 부분 문자열 중 접두사와 접미사 같은 것의 최대 길이를 의미합니다. 

예를 들어, ababab의 경우, pi[0] = 0, pi[1] = 0, pi[2] = 1 (a), ... , pi[5] = 4 (abab) 입니다.

 

그러므로 (전체 길이 - pi[마지막]) 값이 전체 길이로 나눠진다면, 해당 문자열은 (전체 문자열 - pi[마지막]에 해당하는 문자열) 로 가장 많이 나눌 수 있습니다. 

ex) ababab => pi[5] = 4, len(ababab) = 6 => 6 / (6-4) = 3 => ab 3개

그렇지 않은 경우는 나눌 수 없으므로, 정답은 1입니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

string s;
vector<int>pi;

void init()
{
	s = "";
	pi.clear();
	cin >> s;
}

// 실패 함수 얻기
// pi : 접두사, 접미사 같은 최대 길이
vector<int> get_pi()
{
	int m = s.size();
	int j = 0;

	pi.resize(m, 0);

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (1)
	{
		init();
		if (s.size() == 1 && s[0] == '.')
			break;

		pi = get_pi();

		// len % (len - pi[len]) = 0 : 딱 나누어 떨어지는 경우
		// 위가 아닌 경우면 만들 수 없음 (답=1)
		// 최대치를 구하므로 s.size() - pi 벡터의 맨 마지막 원소를 이용함
		// ex) ababab => size = 6, pi[5]=4 => size - pi[5] = 2
		// 최댓값 = size / 2 = 3

		int size = s.size();
		int pattern_size = pi[size - 1];
		int answer = size / (size - pattern_size);

		if (size % (size - pattern_size) != 0) {
			cout << 1 << '\n';
		}
		else
			cout << answer << '\n';
	}
}