from math import gcd from itertools import accumulate n = int(input()) x = [input() for _ in range(n)] x = list(filter(lambda xi: len(xi) > 0, x)) if len(x) == 0: print("true") exit() g = list(accumulate(map(lambda xi: len(xi), x), gcd))[-1] b = x[0][:g] flag = True for xi in x: for p in range(len(xi)): if xi[p] != b[p % g]: flag = False break print("true" if flag else "false")

관찰

길이가 3과 5인 문자열 a, b가 있다고 하자

[a1, a2, a3, b1, b2, b3, b4, b5]

[b1, b2, b3, b4, b5, a1, a2, a3]

이렇게 늘어놓고 봤을 때

a1을 정했을 때 다른 문자들도 다 a1과 같아야 함을 알 수 있다.


6, 9 일 때는 어떨까?

abcabc

abcabcabc

와 같은 형태가 되어야 한다는 것을 알 수 있다.

즉 특정 문자열이 반복되는 형태여야 한다.


풀이

1. 우선 길이가 0인 문자열 예외처리 (있으나 마나)

2. 각 문자열 길이에 대한 gcd (최대 공약수) 를 구한다.

3. 아무 문자열 앞부분에서 길이가 gcd 만큼 땐다. (b라고 하자)  

4. 모든 문자열이 b의 반복인지 확인한다.