16163번 - #15164번_제보

문제

안녕 백준대숲 사람들, 억울한 일이 있어요.

악랄한 :jh05013:이 *회문은 회문아니야!!* 이런 문제를 냈어요. 근데 푼 사람이 너무 많은 거예요!

>내가 이걸 안 풀 순 없지...

생각하면서 고통받으면서 _M_ 어쩌구랑 _offline BIT_‍를 짰다?

근데 :wookje: 솔루션을 보니까 내가 멍청한 거예요ᅲᅲ 백주뉴ᅲᅲ 그들이 절 기만했어요ᅲᅲᅲ

그래서 다시는 낚이지 않겠다고 생각했어요.

근데 얼마 전에 대회를 치면서 *가장 긴 증가하는 팰린드롬 부분수열* 문제를 봤어요.

열심히 생각했는데 _M_ 어쩌구 말고는 생각이 안 나서

>와 이번엔 진짜 _M_ 어쩌구다

생각하면서 열심히 _M_ 어쩌구를 짰다?

근데 이번에도 낚인 거예요ᅲᅲᅲᅲ 사람들 코드 길이가 다 너무 짧아ᅲᅲᅲᅲᅲᅲ 키파 너무 멍청해요ᅲᅲᅲ

이제 키파는 기만자들에게 복수의 철퇴를 날릴 거예요. 그러니까 여러분이 부분 문자열 중 회문인 것의 개수를 구하는 프로그램을 작성해 주세요! 😈

입력

길이가 1 이상 200만 이하인 문자열을 드릴게요. 알파벳 대문자로만 이루어져 있어요!

출력

주어진 문자열의 부분 문자열 중 회문인 것의 개수를 출력해 주세요!

제한

노트

부분 문자열은 원래 문자열에서 연속해야 해요! 즉 `AA`는 `ABCBA`의 부분문자열이 아니에요.

부분 문자열을 가져온 위치가 다르면 다른 문자열로 할게요! 그러니까 예제에서 회문 `A`는 두 번 세어졌어요.

이 문제는 실화예요ᅲᅲᅲ