#15164번_제보

• 문제 설명을 보면 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()

• Dependency: teflib.string.palindrome_radiuses