취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 12871번 문제인 무한 문자열이다.
문제는 아래 링크를 확인하자.

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

두 문자열 s와 t의 길이를 각각 slen, tlen이라 하자. 이 때 f(s)와 f(t)의 공통 주기중 하나는 두 문자열의 길이의 공배수인 slen*tlen이 될 것이다. s와 t를 각각 길이 slen*tlen이 될 때까지 반복시켜 얻은 문자열 S, T를 생각해보자.

f(s)와 f(t)는 각각 s와 t를 끝없이 반복시켜 얻는 문자열이므로 이는 각각 f(S), f(T)와 같게 된다. S와 T의 길이는 slen*tlen으로 서로 같으므로, S와 T가 같다면 f(S)와 f(T)도 같고 S와 T가 다르다면 f(S)와 f(T)도 다르게 된다. 이와 같은 성질을 이용해 S와 T가 서로 같은지를 확인하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

string s1, s2, s11, s22;
int s1len, s2len;
int GCD;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s1 >> s2;
	s1len = s1.length(), s2len = s2.length();

	for (int i = 0; i < s2len; i++) s11 += s1;
	for (int i = 0; i < s1len; i++) s22 += s2;

	if (s11 == s22) cout << 1;
	else cout << 0;
}