사용자 도구

사이트 도구


ps:problems:boj:16163

#15164번_제보

ps
링크acmicpc.net/…
출처BOJ
문제 번호16163
문제명#15164번_제보
레벨플래티넘 5
분류

Manacher

시간복잡도O(n)
인풋사이즈n<2,000,000
사용한 언어Python
제출기록196816KB / 3820ms
최고기록3820ms
해결날짜2021/07/06

풀이

  • 문제 설명을 보면 15927번과 16161번 문제에 대해 언급을 하고 있긴 한데.. 제목에서 언급된 15164번은 이 문제와는 전혀 관계가 없는 문제이다.. 어떤 사연인지 모르겠다.
  • 문제 설명에서 대놓고 말하듯, M어쩌구 (=Manacher's algorithm) 를 써서 팰린드롬 반경을 모두 구하면, 회문의 갯수는 그것들의 합으로 바로 계산된다. Manacher's algorithm으로 팰린드롬 반경을 모두 구하는 데에 O(n), 그것들을 모두 더하는 것도 O(n), 총 시간복잡도는 O(n)이다

코드

"""Solution code for "BOJ 16163. #15164번_제보".

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

Tags: [Manacher]
"""

from teflib import string


def main():
    text = input()
    radiuses = string.palindrome_radiuses(f"#{'#'.join(text)}#")
    print(sum((r + 1) // 2 for r in radiuses))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N P N F᠎ F
 
ps/problems/boj/16163.txt · 마지막으로 수정됨: 2021/07/11 14:48 저자 teferi