[실버 5] 백준 12871 - 무한 문자열 (파이썬)

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

풀이

두 문자열 S와 T가 무한히 반복된다고 할 때, 그 두 무한 문자열이 같은지 확인하는 문제이다.

S = ‘abab’이고 T = ‘ababab’면 무한히 반복하면 둘 다 “abababababab…” 같은 문자열이 된다면 1을 출력하고 아니면 0을 출력한다.

결국 핵심 아이디어는 문자열의 기본 단위를 구해서 비교하는 것이다.

def find_basis(s):
    ...

find_basis함수는 문자열 s의 반복되는 최소 단위를 찾아준다.

예를 들어서 abab가 들어가면 ab를 반환하고, aaaa 가 들어가면 a를 반환한다.

작동 방식은 다음과 같다.

1. 문자열 길이의 약수들을 기준으로 자른다.
2. 해당 길이로 자른 모든 조각이 동일한지 확인한다.
3. 동일하면 그것이 basis다.

S와 T의 basis가 같다면, 그 무한 반복도 같을 수 밖에 없다.

코드

# 백준 12871 - 무한 문자열
# 분류 : 문자열

S = input()
T = input()

def find_basis(s) :
    for i in range(1, len(s) + 1) :
        if len(s) % i != 0 :
            continue

        bad = False
        for j in range(i, len(s), i) :
            if s[j:j + i] != s[:i] :
                bad = True
                break
        
        if not bad :
            return s[:i]

if find_basis(S) == find_basis(T) :
    print(1)
else :
    print(0)