C++で文字列内の特別な回文を数える

文字列strが与えられます。目標は、特殊なパリンドロームであり、長さが1より大きいstrのすべてのサブストリングをカウントすることです。特殊なパリンドロームは、すべて同じ文字または中間の文字のみが異なる文字列です。たとえば、文字列が「baabaa」の場合、元の文字列のサブ文字列である特別な回文は「aa」、「aabaa」、「aba」、「aa」です

例を挙げて理解しましょう。

入力 − str =” abccdcdf”

出力 −文字列内の特殊な回文の数は− 3

説明 −特殊なパリンドロームである部分文字列は、−「cc」、「cdc」、「dcd」です

入力 − str =” baabaab”

出力 −文字列内の特殊な回文の数は− 4

説明 −特殊な回文である部分文字列は、−「aa」、「aabaa」、「aba」、「aa」です

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

• アルファベットの文字列を作成し、その長さを計算します。さらに処理するためにデータを関数に渡します。

• 一時変数のカウントとiを宣言し、それらを0に設定します

• 文字列のサイズの配列を作成し、0で初期化します。

• 文字列の長さより短くなるまでWHILEを開始します

• while内で、変数をtotalに1に設定し、変数jをi+1に設定します

• str [i] =str [j]ANDjが文字列の長さよりも小さくなるまで別のWHILEを開始します

• while内で、合計を1ずつ増やし、jを1ずつ増やします

• カウントをカウント+（合計*（合計+ 1）/ 2、arr [i]を合計、iをj

  として設定します。

• 文字列の長さまでjから1までループFORを開始します

• str [j] =str [j-1]かどうかを確認してから、arr[j]をarr[j-1]

  に設定します。

• 変数tempをstr[j-1]に設定し、j> 0 ANDj<文字列の長さの1つ少ないANDtemp=str [j + 1] AND sr [j]！=tempかどうかを確認してから、countをcount+として設定します。 min（arr [j-1]、arr [j + 1]）

• カウントをカウントに設定します-文字列の長さ

• カウントを返す

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
   int count = 0, i = 0;
   int arr[len] = { 0 };
   while (i < len){
      int total = 1;
      int j = i + 1;
      while (str[i] == str[j] && j < len){
         total++;
         j++;
      }
      count += (total * (total + 1) / 2);
      arr[i] = total;
      i = j;
   }
   for (int j = 1; j < len; j++){
      if (str[j] == str[j - 1]){
         arr[j] = arr[j - 1];
      }
      int temp = str[j - 1];
      if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
         count += min(arr[j-1], arr[j+1]);
      }
   }
   count = count - len;
   return count;
}
int main(){
   string str = "bcbaba";
   int len = str.length();
   cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
   return 0;
}

出力

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

Count of special palindromes in a String are: 3