[백준 12871/c++] 무한 문자열

문자열 a와 b를 무한히 늘렸을때 두 문자열은 같은지를 묻는 문제이다

a길이와 b길이의 최소공배수를 구하고 그 길이가 될때까지 각각 자기복제를 하여 새로 만든 두 문자열이

같은지를 비교하면 되는 문제이다

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

12871번: 무한 문자열

#include <bits/stdc++.h>
using namespace std;

int gcd(int x, int y){
	int z;
	while(y!=0){
		z=x%y;
		x=y;	
		y=z;
	}
	return x;
}

int lcm(int x, int y){
	return x*y/gcd(x, y);
}

int main(){
	
	string a, b;
	
	cin >> a >> b;
	
	string atm=a;
	string btm=b;
	
	int al=a.length();		
	int bl=b.length();
	
	int ablcm=lcm(al, bl);	
	
	if(a==b){
		cout << 1 << "\n";
		return 0;
	}
	
	while(al!=ablcm){	
		atm+=a;
		al+=a.length();
	}
	
	while(bl!=ablcm){	
		btm+=b;
		bl+=b.length();
	}

	
	if(atm==btm){
		cout << 1 << "\n";
	} else {
		cout << 0 << "\n";
	}
	
	return 0;
}