백준 4354 - 문자열 제곱 (Python)

KMP 알고리즘의 failure function을 사용하면 됩니다.

전체 코드

import sys

input = sys.stdin.readline

def make_table(P):
    P_SIZE = len(P)
    t = [0] * P_SIZE
    j = 0
    
    for i in range(1, P_SIZE):
        while j > 0 and P[i] != P[j]:
            j = t[j - 1]
        
        if P[i] == P[j]:
            j += 1
            t[i] = j
    
    return t[-1]
                
while True:
    a = input().replace('\n', '')
    
    if a == '.':
        break
    
    len_a = len(a)
    len_match = len_a - make_table(a)
    
    if len_a % len_match != 0:
        print(1)
        continue
    
    print(len_a // len_match)