C++のインデックス範囲内のパリンドローム部分文字列の数

文字列と開始から終了までの範囲が与えられ、タスクは、指定された範囲に存在するパリンドローム部分文字列の数を計算することです。回文文字列は、nitin、abaなどの文字列の前後から類似している文字列です。

例

入力- InputString ="cccaabbbdee"、start =2、end =6;

出力- インデックス範囲7のパリンドローム部分文字列の数

説明- 範囲と文字列が指定されているため、開始ポインタである2、つまり「c」から6、つまり「b」まで文字列のトラバースを開始します。したがって、サブ文字列は「caabb」になります。したがって、パリンドロームの部分文字列は、「c」、「a」、「a」、「b」、「b」、「aa」、および「bb」です。したがって、回文部分文字列の数は7です。

入力- InputString ="lioaabbbdee"、start =0、end =2;

出力- インデックス範囲3のパリンドローム部分文字列の数

説明- 範囲と文字列が与えられているので、開始ポインタである0、つまり「l」から2、つまり「o」まで文字列のトラバースを開始します。したがって、サブ文字列は「lio」です。したがって、回文部分文字列は「l」、「i」、および「o」です。したがって、回文部分文字列の数は3です。

以下のプログラムで使用されているアプローチは次のとおりです

• 任意のサイズと変数の開始から終了までの範囲の文字列を宣言します。
• さらに処理するために、データをpalindrome_index（arr、InputString）という名前の関数に渡します
• 関数内で、checkedという名前の別の配列を配列サイズで宣言します。
• ループFORiを0から配列の長さまで開始します
• ループ内で、0から配列の長さまで別のLoopF​​ORjを開始します
• ループ内で、checkをcheck [i] [j]=0およびarr[i][j]=0として設定します
• 長さ-1からiが0より大きくなるまでループFORiを開始します
• ループ内で、iのcheckとarrを1に設定してから、i+1から配列の長さまで別のループFORjを開始します
• ループ内で、iiの文字列がjの文字列と等しいかどうかを確認し、i +1がj-1より大きいか、check [i + 1] [j-1]）が0に等しくないかどうかを確認してから、check[i]を設定します。 [j]を1ELSEとして設定し、check [i] [j]を0として設定してから、arr [i] [j] =arr [i] [j --1] + arr [i + 1] [j]--arr[i]を設定します。 + 1][j-1]+チェック[i][j]
• 2次元配列を開始と終了として印刷します。

例

import java.io.*;
class testqwe {
   static void palindrome_index(int arr[][], String s) {
      int length = s.length();
      int[][] check = new int[length + 1][length + 1];
      for (int i = 0; i <= length; i++) {
         for (int j = 0; j <= length; j++) {
            check[i][j] = 0;
            arr[i][j] = 0;
         }
      }

      for (int i = length - 1; i >= 0; i--) {
         check[i][i] = arr[i][i] = 1;
         for (int j = i + 1; j < length; j++) {
            if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
               check[i][j] =1;
            } else {
               check[i][j] =0;
            }
            arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
         }
      }
   }
   public static void main(String args[]) {
      String InputString = "cccaabbbdee";
      int[][] arr;
      arr = new int[50][50];
      palindrome_index(arr, InputString);
      int start = 2;
      int end = 6;
      System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
   }
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of Palindromic substrings in an Index range 7