BOJ-11585 - Python

환형 문자열에서 특정 문자열을 찾아 나올 수 있는 확률을 기약 분수 형태로 출력하는 문제. 두 문자열을 입력받은 후 한 문자열을 2배로 한 후, 마지막 문자를 제거한 문자열에서 다른 문자열을 KMP 알고리즘을 이용하여 찾도록 풀었다. 마지막 문자를 제거하는 이유는 입력되는 문자열이 동일 시 추가적으로 한 개가 더 늘기 때문이다. 기약분수화는 fractions의 Fraction을 이용하였으며 모든 경우에서 찾을 수 있을 때 1로 나오는 것을 예외처리하여 풀었다.

from fractions import Fraction

def KMP(ori, pat):
    lt = n * 2 - 1
    lp = n
    lps = getLPS(pat, n)

    ans = 0

    i = 0
    j = 0
    while i < lt:
        if ori[i] == pat[j]:
            i += 1
            j += 1
        elif ori[i] != pat[j]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

        if j == lp:
            ans += 1
            j = lps[j-1]

    return ans

def getLPS(pat, length):
    lps = [0 for _ in range(length)]

    j = 0
    i = 1
    while i < length:
        if pat[i] == pat[j]:
            j += 1
            lps[i] = j
            i += 1
        else:
            if j != 0:
                j = lps[j-1]
            else:
                lps[i] = 0
                i += 1
    return lps

n = int(input())
pat = input().replace(' ', '')
origin = input().replace(' ', '') * 2

kmp = KMP(origin[:n*2-1], pat)
frac = Fraction(kmp, n)
print("1/1" if frac == 1 else frac)

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn