「BOJ 12871」 무한 문자열

링크

• 12871번: 무한 문자열

---

문제

문자열 \( s \)가 있을 때, \( f(s) \) 는 \( s \)를 무한번 붙인 문자열로 정의한다. 예를 들어, \( s \) = "abc" 인 경우에 \( f(s) \) = "abcabcabcabc..."가 된다.

다른 문자열 \( s \)와 \( t \)가 있을 때, \( f(s) \) 와 \( f(t) \) 가 같은 문자열인 경우가 있다. 예를 들어서, \( s \) = "abc", \( t \) = "abcabc"인 경우에 \( f(s) \) 와 \( f(t) \) 는 같은 문자열을 만든다.

\( s \)와 \( t \)가 주어졌을 때, \( f(s) \) 와 \( f(t) \) 가 같은 문자열을 만드는지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 \( s \), 둘째 줄에 \( t \)가 주어진다. 두 문자열 \( s \)와 \( t \)의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다. 

출력

첫째 줄에 \( f(s) \)와 \( f(t) \)가 같으면 1을, 다르면 0을 출력한다.

---

풀이

\( f(s) \) 와 \( f(t) \) 가 같으려면, 원래의 두 문자열에서 나타나는 반복되는 가장 짧은 패턴이 일치해야 한다.

 

\( s \)가 일정한 문자열 패턴 \( X \)가 \( a \) 번 반복되는 형태이며, \( t \)가 패턴 \( X \)가 \( b \) 번 반복되는 형태라면, 이들을 각각 복사해서 만든 패턴 \( X \)가 \( ab \) 번 반복되는 형태의 문자열 \( s' \) 과 \( t' \) 이 서로 같게 나타나야 \( f(s) \) 와 \( f(t) \) 처럼 무한히 반복될 때도 동일하게 나타난다.

 

간단히 \( s \) 를 \( len(t) \) 번, \( t \) 를 \( len(s) \) 번 반복한 문자열이 서로 같은 지 확인해 주면 된다.

---

코드

a = input()
b = input()
lenA = len(a)
lenB = len(b)
a *= lenB
b *= lenA
print(int(a == b))

---

난이도

2022년 1월 8일 기준 12871번의 난이도는 실버 5입니다.