부분 회문 쌍 찾기 |
---|
알파벳 소문자로 구성된 문자열 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 해야 한다. |
입력 | |
---|---|
첫째 줄에 알파벳 소문자로 구성된 문자열 S가 주어진다. S에는 공백이 없으며 S의 최대 길이는 260 미만이다. |
출력 | |
---|---|
첫째 줄에 부분 회문의 쌍의 개수를 출력한다. 예시2의 경우, (a1, a2a3), (a1a2, a3), (a1, a2), (a2, a3), (a1, a3) 이므로 부분 회문 쌍의 개수는 5다. |
예시 | |||
---|---|---|---|
1 | 입력 | aa | |
출력 | 1 | ||
2 | 입력 | aaa | |
출력 | 5 | ||
3 | 입력 | abacaba | |
출력 | 36 |