[Python]문자열 알고리즘1 백준 4354

   문제

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

문자열을 특정패턴의 반복으로 만들어 낼수있는가를 묻는 문제이다.

특정패턴을 반복하여 만들수 있는가는 이전에 사용했던 실패함수 부분일치테이블을 

생성하여 확인할 수 있다.

특정 패턴의 반복만으로 만들어지는경우와 테이블을 살펴보자

ababab

001234

abcabc

000123

aaaaa

01234

len(T) - table[len(T)-1] 의 값이 패턴의 길이라는것을 알수있다.

불가능 할때도 살펴보자.

ababc

00120

 table[len(T)-1]이 0인경우 반복할 패턴이 없는것이다..

aabaa

00012

table[len(T)-1]이 0은 아니지만 패턴의 길이로 나누어 떨어지지 않는다면 패턴이 없다고

 볼수있다.

두경우 모두 나머지가 0이 아님을 볼수있다.

이제 구현해 보자.

부분 일치 테이블을 구하고 그 값을 이용하여 패턴의 길이를 구한뒤  

(문자열의 길이//패턴길이)를 구하면된다.

while 1:
    s=input()
    if s==".":
        break
    else:
        s_len=len(s)
        p_table=[0 for _ in range(s_len)]
 
        #실패함수
        j=0
        for i in range(1,s_len):
            while j>0 and s[i]!=s[j]:
                j=p_table[j-1]
            if s[i]==s[j]:
                j+=1
                p_table[i]=j
 
 
        p_len=s_len-p_table[s_len-1]#패턴길이
        
        if s_len%p_len==0:#패턴의 길이로 나누어떨어진다면
            print(s_len//p_len)
        else:
            print(1)