C++で他のバイナリ文字列とのXORが0である巡回置換の数

2つのバイナリ文字列（たとえば、1と0の組み合わせを含むstr_1とstr_2）が与えられます。タスクは、最初に、文字列str_1から可能なさまざまな順列の「SET」と言うセットを形成することです。次に、のXOR演算を実行します。要素がバイナリ文字列str_2で設定され、XORが0を返しているかどうかを確認します。はいの場合は、ケースを検討します。それ以外の場合は無視します。

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

例

入力- string str_1 ="1111"、string str_2 ="1111"

出力- 他のバイナリ文字列とのXORを0とする巡回置換の数は次のとおりです。4

説明- 文字列str_2を使用してセットを作成し、セットは{1111}になります。次に、文字列str_1を使用してXOR演算を実行し、{1111} ^“ 1111” =0となるように設定します。文字列str_2には4つの類似した要素があるため、4つの異なる順列を形成できるため、出力は4になります。

入力- string str_1 ="1101"、string str_2 ="1101"

出力- 他のバイナリ文字列とのXORを0とする巡回置換の数は次のとおりです。1

説明- 文字列str_2を使用してセットを作成し、セットは{1101、1110、1011、0111}になります。次に、文字列str_1を使用してXOR演算を実行し、形成されたセットを実行します。

{1101} ^ 1101 =0

{1110}^1101は0と等しくありません

{1011}^1101は0と等しくありません

{0111}^1101は0と等しくありません

0を1つしか達成できなかったため、カウントは1です。

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

• 2つのバイナリ文字列（たとえば、str_1とstr_2）を入力し、それらを関数Cyclic_permutation（）に渡してさらに処理します。
• 結果を格納する一時変数を作成し、str_2をstr_2 + str_2として設定してから、str_2をstr_2.substr（0、str_2.size（）-1）として設定します。
• 文字列型変数strを作成し、str_1とstr_2の組み合わせに設定してから、文字列strの長さを計算します。文字列strの長さの配列を作成します。
• 文字列strと配列を引数として関数に渡すことにより、関数check（）を呼び出します。
• 関数内
  • 2つの変数の開始と終了を宣言し、それらを0に設定します
  • 文字列の長さを計算します。
  • 文字列-1のiから長さまでループFORを開始し、iがendより大きいかどうかを確認してから、startをi、endをiに設定します。ここで開始します。終了は文字列の長さ未満であり、str[end-start]はstr[end]と等しく、endの値を1ずつ増やします
  • ここで、arr[i]をendとして設定します-開始して終了を1デクリメントします
  • それ以外の場合は、一時変数tempを作成し、i --startとして設定し、ifarr[temp]がend--i+ 1未満であることを確認してから、arr[i]をarr[temp]として設定します。それ以外の場合は、startをiに設定し、endWHILEendが文字列の長さ未満であるANDstr[end-start] as str [end]を設定し、endを1インクリメントし、arr[i]をend--startとして設定し、endを1だけデクリメントします。 。
• ループFORをiから1まで開始し、それまで文字列str -1の長さを確認し、arr[i]が文字列str_1の長さと等しいかどうかを確認してからカウントを1ずつ増やします
• 返品数
• 結果を印刷する

例

#include <bits/stdc++.h>
using namespace std;

void check(string str, int arr[]) {
   int start = 0, end = 0;
   int len = str.length();

   for (int i = 1; i <= len - 1; i++) {
      if (i > end) {
         start = i;
         end = i;
         while (end < len && str[end - start] == str[end]) {
            end++;
         }
         arr[i] = end - start;
         end--;
      } else {
         int temp = i - start;
         if (arr[temp] < end - i + 1) {
            arr[i] = arr[temp];
         } else {
            start = i;
            while (end < len && str[end - start] == str[end]) {
               end++;
            }
            arr[i] = end - start;
            end--;
         }
      }
   }
}

int cyclic_permutation(string str_1, string str_2) {
   int count = 0;
   str_2 = str_2 + str_2;
   str_2 = str_2.substr(0, str_2.size() - 1);

   string str = str_1 + "$" + str_2;
   int len = str.length();
   int arr[len];
   check(str, arr);

   for (int i = 1; i <= len - 1; i++) {
      if (arr[i] == str_1.length()) {
         count++;
      }
   }
   return count;
}
int main() {
   string str_1 = "1111";
   string str_2 = "1111";
   cout << "Count of cyclic permutations having XOR with other binary string as 0 are: " << cyclic_permutation(str_1, str_2);
   return 0;
}

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

出力

Count of cyclic permutations having XOR with other binary string as 0 are: 4