[Algorithm]the shortest repetitive pattern in a string

문제 배경:

string이 주어져있을 때, string의 period를 다음과 같이 정의하자.

substring의 반복으로 string을 만들 수 있을 때, 가장 짧은 substring의 길이를 period라 하자.

ex)

abab -> ab를 2번 반복하거나 abab를 1번 -> ab가 더 짧고, 그 때의 길이가 2이므로 period는 2

abcabcabd -> abcabcabd를 1번 -> period는 9

 

문제:

string이 argument로 들어왔을 때, string의 period를 반환하는 함수를 작성하여라.

 

해결:

 

비고:

-counter을 해석하는게 가장 관건이다. 

예를 들어 abababab의 경우

  -counter[3] = 2라는 것은, s[:4](즉 index가 0에서 3까지, substr=abab)에서 substr[:2]와 substr[-2:]가 같다는 말, 

  -counter[4] = 3라는 것은, s[:5](즉 index가 0에서 4까지, substr=ababa)에서 substr[:3]와 substr[-3:]가 같다는 말

-즉 counter가 for i in range(1,len(s))를 돌면서 prefix=suffix되는 가장 긴 길이를 보관함

-난이도 상