C++로 주어진 문자열의 겹치지 않는 회문 부분 문자열 쌍 개수 구하기

문자열이 입력으로 주어졌을 때, 이 문자열에서 겹치지 않는(non-overlapping) 회문 부분 문자열 쌍의 개수를 구하는 것이 목표입니다. 2차원 배열 arr[i][j]의 값은 i부터 j까지의 부분 문자열이 회문이면 true, 그렇지 않으면 false가 됩니다. 문자열에서 가능한 조합을 하나씩 만들어 보고, 각 쌍이 조건을 충족하는지 확인하는 방식으로 문제를 해결할 수 있습니다.

예제로 이해하기

입력: ABC

출력: 겹치지 않는 회문 부분 문자열 쌍의 개수는 3

설명: 가능한 쌍은 (A)(B)(C), (A)(BC), (AB)(C), (ABC) 입니다.

입력: ABCD

출력: 겹치지 않는 회문 부분 문자열 쌍의 개수는 8

설명: 가능한 쌍은 (A)(B)(C)(D), (A)(B)(CD), (A)(BC)(D), (A)(BCD), (AB)(C)(D), (AB)(CD), (ABC)(D), (ABCD) 입니다.

아래 프로그램에서 사용된 접근 방식

• 문자열을 입력받아 pair_count(text) 함수에 전달하여 처리합니다.
• 먼저 크기 100×100의 boolean 2차원 배열 arr[ ][ ]을 생성하고, 하향식(bottom-up) 방식으로 값을 채워 나갑니다. 동시에 입력 문자열(text)을 문자 배열로 변환합니다.
• 배열은 arr[i+1][j-1] 값을 검사하는 방식으로 계산됩니다. 이 값이 true이고 str[i]가 str[j]와 같으면 arr[i][j]를 true로 설정하고, 그렇지 않으면 false로 만듭니다.
• 그다음 start[ ]와 end[ ] 배열을 초기화합니다. start[i]에는 인덱스 i를 포함하여 왼쪽에 존재하는 회문의 개수가 저장되고, end[i]에는 인덱스 i를 포함하여 오른쪽에 존재하는 회문의 개수가 저장됩니다.
• 마지막으로 0부터 str.length() - 1까지 루프를 반복하면서, 루프 내부에서 result에 start[i] * end[i + 1]의 곱을 더하여 최종 결과를 계산합니다.

예제 코드

import java.io.*;
import java.util.*;
class tutorialPoint {
   static int SIZE = 100;
   static int pair_count(String str) {
      boolean arr[][] = new boolean[SIZE][SIZE];
      char[] ch = str.toCharArray();
      for (int i = 0; i < ch.length; i++) {
         for (int j = 0; j < ch.length; j++) {
            arr[i][j] = false;
         }
      }
      for (int j = 1; j <= ch.length; j++) {
         for (int i = 0; i <= ch.length - j; i++) {
            if (j <= 2) {
               if (ch[i] == ch[i + j - 1]) {
                  arr[i][i + j - 1] = true;
               }
            } else if (ch[i] == ch[i + j - 1]) {
               arr[i][i + j - 1] = arr[i + 1][i + j - 2];
            }
         }
      }
      int start[] = new int[str.length()];
      int end[] = new int[str.length()];
      start[0] = 1;
      for (int i = 1; i < str.length(); i++) {
         for (int j = 0; j <= i; j++) {
            if (arr[j][i] == true) {
               start[i]++;
            }
         }
      }
      end[str.length() - 1] = 1;
      for (int i = str.length() - 2; i >= 0; i--) {
         end[i] = end[i + 1];
         for (int j = str.length() - 1; j >= i; j--) {
            if (arr[i][j] == true) {
               end[i]++;
            }
         }
      }
      int result = 0;
      for (int i = 0; i < str.length() - 1; i++) {
         result = result + start[i] * end[i + 1];
      }
      return result;
   }

   public static void main(String[] args) {
      Scanner scan = new Scanner(System.in); // ABCD
      String text = scan.next();
      System.out.println("겹치지 않는 회문 부분 문자열 쌍의 개수는\t" + pair_count(text));
   }
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

겹치지 않는 회문 부분 문자열 쌍의 개수는 8