====== #15164번_제보 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:string#palindrome_radiuses|teflib.string.palindrome_radiuses]]

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