4354_문자열제곱

https://www.acmicpc.net/problem/4354

4354번: 문자열 제곱

 

 

KMP 알고리즘을 활용해서 문제를 풀 수 있다.

 

a란 이름의 str이 입력된다고 생각해보자.

 

a+a 문자열을 하나 만들 수 있을 것이다.

 

만약 abcd가 들어온다면  abcdabcd를 만들어준다.

 

이 a+a 문자열에서 a가 시작되는 부분을 구해준다.

 

abcdabcd라면 abcd가 다시 시작되는 부분은 5번째일 것이다 index로 나타내면 4이다.

aaaa가 들어온다면 aaaaaaaa이므로 aaaa가 나오는 부분은 2번째, index로는 1일 것이다.

 

이 나오는 값이 반복되는 주기이므로 str길이에서 나누어주면 된다.

 

def KMP(t,p):
    lp = len(p)
    k = [0] * lp

    j=0
    for i in range(1,lp):
        while j>0 and p[i] != p[j]:
            j =k[j-1]
        if p[i]==p[j]:
            j+=1
            k[i] = j
    j=0
    for i in range(1,len(t)):
        while j>0 and t[i] != p[j]:
            j = k[j-1]
        if t[i] == p[j]:
            if j == lp-1:
                return i-lp+1
            else:
                j+=1


while True:
    str = input()
    if str =='.':
        break
    print( len(str) // KMP(str+str,str))