O(n)에 팰린드롬 개수를 구하는 알고리즘이 있어요!!

Manacher 알고리즘 이용하여 풀 수 있읍니다. Dynamic Programming 사용하는 것은 문자열 갯수가 최대 2,000,000개라 메모리 초과 날 수 있읍니다.

문자열 최대 갯수를 고려할 때 부분 문자열의 모든 팰린드롬 개수는 int 범위를 넘어 갈 수도 있읍니다.