소주 만병만 주소 timer 1s memory - MB

회문이란 앞으로 읽으나 뒤로 읽으나 같은 문자열인 것을 말한다. 예를 들어 "Z", "TOT", "MADAM", "소주 만병만 주소"와 같은 것들은 회문이지만, "ADCDE"는 회문이 아니다.

문자열이 주어지면, 회문이 되는 부분 문자열의 개수를 구하는 프로그램을 작성하자. 단, 부분 문자열을 만들 때 각 문자의 상대적인 순서는 바꿀 수 없다. 즉, "BCA"에서 "BA"는 부분 문자열 이지만, "AB"는 부분 문자열이 아니다.

예를 하나 들어보자. "ABA"에서 회문은 A1, B2, A3, A1A3, A1B2A3의 다섯 가지가 존재한다. "AAAA"의 경우 이보다 훨씬 많은데, A1, A2, A3, A4, A1A2, A1A3, A1A4, A2A3, A2A4, A3A4, A1A2A3, A1A2A4, A1A3A4, A2A3A4, A1A2A3A4 의 15가지 경우가 존재한다. 즉, 문자열 구성이 같아도 조합이 다르다면 서로 다른 것으로 센다.