12871 무한문자열

간단한 문자열 문제

두 문자열을 각각 무한번 붙였을때

두 문자열이 같은 문자열을 만드는지 체크하는 문제

https://www.acmicpc.net/problem/12871

1. 문제

---

간단 설명

문자열 s와 t가 있을 때

문자열 s를 무한번 반복시킨 f(s)와

문자열 t를 무한번 반복시킨 f(t)가 같은 문자열을 만드는지 확인하는 문제

2. 문제 분석

---

주의점

• 무한번 문자열을 반복시키는건 불가능하므로, 언제까지 문자열을 붙일것인지 정하는것이 중요

필요변수

문자열 s, t 최대 50글자, 알파벳 소문자로만 이루어짐

무한번 붙인 문자열 f_s, f_t

알고리즘

1. 문자열 s와 t를 입력받는다
2. 문자열 s와 t의 길이를 구해 두 수의 최소 공배수를 구한다
3. 최소공배수만큼 문자열을 늘린다. 문자열의 수를 일치시킴
4. f_s와 f_t가 일치하는지 확인후 출력

3. 소스코드

---

#include <iostream>
#include <string>
#include <algorithm>
#include <numeric> // C++ 17 부터 추가된 numeric 라이브러리의 최소공배수 함수인 LCM 이용

using namespace std;

bool CheckString(string s, string t) {
	int lcm_num =  lcm(s.size(),t.size()); // 직접 구해도 되지만 LCM 함수를 이용해봄

	string f_s, f_t;
	
	for (int i = 0; i < lcm_num / s.size(); i++) // 몇번 더해줘야 최소공배수 일치될지
		f_s += s;
	
	for (int i = 0; i < lcm_num / t.size(); i++)
		f_t += t;

	if (f_s == f_t) {
		return 1;
	}

	return 0;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	string s, t;
	cin >> s >> t;

	cout << CheckString(s, t);

	return 0;
}

무한번을 늘리는것은 불가능하므로

언제까지 늘릴지를 결정하는것이 문제 해결의 핵심