[백준/BOJ] 백준 4354번 : 문자열 제곱

www.acmicpc.net/problem/4354

4354번: 문자열 제곱

KMP알고리즘을 이용하여 문제를 해결했다. pi에 해당 길이까지 접두사도 되고, 접미사도 되는 문자열의 최대 길이를 저장하고, s.size() - pi[s.size() - 1]를 통해 a의 길이(a_size)를 구한뒤, s.substr(0, a_size)를 통해 a를 구하고, 여기서 구한 a로 s=a^n가 가능한지 판단하고(불가능하다면 a는 s이다), 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

vector<int> pi(1000000); //접두사도 되고 접미사도 되는 문자열의 최대 길이 저장
string s;

//KMP알고리즘을 이용한다
//알고리즘 문제해결 전략2 책 KMP알고리즘 공부 실습

void Pre()
{
	for (int i = 0; i < 1000000; i++)
		pi[i] = 0;
}

void Make_pi()
{
	int s_size = s.size();

	int begin = 1;
	int matched = 0;

	while (begin + matched < s_size) //확인하는곳이 s_size보다 작아야된다
	{
		if (s[begin + matched] == s[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}

		else
		{
			if (matched == 0)
			{
				begin++;
				matched = 0;
			}

			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
}

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

	while (1)
	{
		cin >> s;

		if (s == ".")
			break;

		Pre();
		Make_pi();

		int a_size = s.size() - pi[s.size() - 1];
		string a = s.substr(0, a_size); //a를 구한다

		int a_cnt = s.size() / a_size;

		bool check = true;

		if (pi[s.size() - 1] == 0) //접두사도 되고 접미사도 되는게 없을때
			cout << 1 << "\n";

		else if (s.size() % a_size != 0) //길이로 s=a^n으로 만들 수 없을때
			cout << 1 << "\n";

		else
		{

			for (int i = 0; i <= s.size() - a_size; )
			{
				if (a != s.substr(i, a_size)) //s.substr(i, a_size) 부분이 a로 이뤄지지 않았을때
				{
					check = false;
					break;
				}

				i = i + a_size;
			}


			if (check == false)
				cout << 1 << "\n";

			else
				cout << a_cnt << "\n";
		}
	}

	return 0;
}