C++에서 주어진 문자열의 겹치지 않는 회문 하위 문자열의 쌍을 셉니다.

입력이 문자열로 주어지면 주어진 입력 문자열의 겹치지 않는 회문 하위 문자열 쌍의 수를 찾는 작업입니다. arr[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 arr[ ][ ] 크기의 부울 2D 배열이 생성 및 유지되어 상향식 접근 방식으로 채워지고 입력 문자열(텍스트)이 문자 배열로 변환됩니다.
• 배열은 arr[i+1][j-1] 값을 확인하여 계산됩니다. 값이 true이고 str[i]가 str[j]와 같으면 arr[i]를 만듭니다. [제이] 사실이다. 그렇지 않으면 arr[i][j]의 값이 false가 됩니다.
• 그 후 start[ ]와 end[ ]가 초기화되고 start[i]는 인덱스(i 포함) 왼쪽에 있는 회문 수의 회문 수를 저장하고 end[i]는 해당 숫자의 회문 수를 저장합니다. 인덱스 오른쪽에 있는 요소 수(i 포함)
• 루프는 0에서 str.length() - 1까지 반복되고 루프 내에서 결과는 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("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text));
   }
}

위의 코드를 실행하면 다음 출력이 생성됩니다 -

출력

Count pairs of non-overlapping palindromic sub-strings is 8