테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 문자열 제곱 ======

===== 풀이 =====
  * [[ps:문자열#반복 찾기|문자열의 반복 패턴]]을 찾자.
  * 링크에서 설명했듯이, S를 A^n 형태로 표현할 수 있는지 여부와 그때의 가장 짧은 A의 길이는, fail함수를 이용해서 구할수도 있지만, 그냥 builtin str.find 함수를 사용해서 훨씬 빠르게 구할수 있다. 시간복잡도는 kmp와 같은 O(n)이지만, kmp를 구현해서 풀었을때에는 2000ms이상 걸리던 것이 str.find를 이용하면 200ms 이내에 풀린다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 4354. 문자열 제곱".

- Problem link: https://www.acmicpc.net/problem/4354
- Solution link: http://www.teferi.net/ps/problems/boj/4354
"""


def main():
    while (s := input()) != '.':
        print(len(s) // (s + s).find(s, 1))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}