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]をチェックすることによって計算されます。値が真で、str[i]がstr[j]と同じである場合、arr[i]を作成します。 [j]本当。それ以外の場合、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