[BOJ] 1498 - 주기문 (Python)

 

 

아이디어

 

KMP 알고리즘으로 패턴의 길이를 찾아 나간다.

 

 

풀이

 

i+1은 인덱스 i까지 문자열의 길이를 나타내고, j는 그 문자열에서 접두사와 접미사가 일치하는 부분의 길이를 나타낸다.

i+1에서 j를 빼면 패턴의 길이를 알 수 있는데, 이때 문자열 길이 i+1가 패턴의 길이 i+1-j로 나누어 떨어져야 한다.

값이 나누어 떨어지면서 그 몫(패턴의 수)이 1보다 크면 주기문이므로 해당 문자열의 길이와 패턴의 수를 출력한다.

 

def solution():
    S = input()
    N = len(S)
    lps = [0]*N
    j = 0
    for i in range(1, N):
        while j > 0 and S[i] != S[j]:
            j = lps[j-1]
        if S[i] == S[j]:
            j += 1
            lps[i] = j
            a, b = (i+1)%(i+1-j), (i+1)//(i+1-j)
            if a == 0 and b > 1:
                print(i+1, b)

solution()

 

 

결과값을 문자열로 저장해두었다가 한번에 출력하는 코드는 더 빨랐지만 메모리가 더 많이 사용되었다.

# 메모리를 더 많이 사용하나 더 빠른 코드
for i in range(1, N):
    ...
    res.append(f'{i+1} {int(n)}')
print(*res, sep='\n')