문제
풀이
KMP의 failure function을 통해, 해당 문자에 prefix == suffix인 최대길이를 확인한다.(index 1부터 counting하므로, aaaa -> a[3] = 4가 아니라 3이다.)
기존 문자열의 길이에 len(s)-1의 index에 위치한 것의 prefix == suffix인 pi[len(s)-1]를 빼면, 최소 반복 길이를 구할 수 있다.
이를 전체 문자열의 길이에 나누면 원하는 정답을 도출해낼 수 있다.
abcdabc와 같이 pi[len(s)-1] = 3이지만, 제곱수가 1인 경우 역시도 7//4 = 1로 원하는 답을 얻을 수 있다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys
from math import *
def failure_function(s):
pi = [0] * len(s)
j = 0
for i in range(1, len(s)):
while(j>0 and s[i] != s[j]):
j = pi[j-1]
if(s[i] == s[j]):
j = j+1
pi[i] = j
return pi
while(True):
s = input()
if(s == "."):
break
pi = failure_function(s)
min_size = len(s) - pi[len(s)-1]
if(len(s) % min_size == 0):
print(len(s)//min_size)
else:
print(1)
