알파벳 소문자로 구성된 문자열 S가 주어질 때 S에서 서로 겹치지 않은 부분 회문 쌍의 개수를 구하는 프로그램을 작성하시오.

S[a...b], S[x...y]가 문자열 S의 부분 문자열이고 회문이면서 ‘1 ≤ a ≤ b < x ≤ y ≤ S의 길이’ 을 만족할 때, 이 부분 회문 S[a...b], S[x...y] 쌍의 개수를 찾아야 한다.

회문은 왼쪽부터 읽으나 오른쪽부터 읽으나 동일하게 읽히는 문자열이다. 또한 S[i...j] (1 ≤ i ≤ j ≤ S의 길이)은 문자열 S에서 i번째 문자부터 j번째 문자까지의 부분 문자열이다. 예를 들어 S가 ‘abacaba’일 때 S[2...4]는 ‘bac’ 이다.

※ 입력받은 문자열의 길이는 strlen() 함수를 이용하면 된다. 만약, char 형 배열 a를 통해 문자열을 입력받았다면 n=strlen(a); 하면 n에 배열 a에 저장된 문자열의 길이가 자동으로 계산되어 저장된다. strlen() 함수는 string.h 헤더 파일을 include 해야 한다.