사용자 도구

사이트 도구


ps:problems:boj:4354

문자열 제곱

ps
링크acmicpc.net/…
출처BOJ
문제 번호4354
문제명문자열 제곱
레벨플래티넘 5
분류

문자열

시간복잡도O(t*n)
인풋사이즈t<=?, n<=1,000,000
사용한 언어Python 3.11
제출기록36308KB / 168ms
최고기록168ms
해결날짜2022/12/16

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
L U U J᠎ L
 
ps/problems/boj/4354.txt · 마지막으로 수정됨: 2022/12/16 14:40 저자 teferi