백준 4354번: 문자열 제곱 (Python)

접근

KMP 알고리즘을 이용하여 KMP table 구할 수 있다. 이 table 의 가장 마지막 숫자를 확인하고, 문자열 전체 길이를 이 수로 나누었을 때 나누어 떨어지지 않으면 반복이 0회, 즉 답이 1이고, 나누어 떨어진다면 그 몫이 답이다.

코드

import sys


def kmptable(a):
    n = len(a)
    table = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and a[i] != a[j]:
            j = table[j - 1]
        if a[i] == a[j]:
            j += 1
            table[i] = j
    return table


while 1:
    p = sys.stdin.readline().rstrip()
    if p == '.':
        break
    table = kmptable(p)
    mod = len(p) - table[-1]
    if len(p) % mod == 0:
        print(len(p) // mod)
    else:
        print(1)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!