C++で他のバイナリ文字列とのXORが0となる巡回置換の個数を求める方法

0と1の組み合わせで構成される2つのバイナリ文字列 str_1 と str_2 が与えられたとします。まず、文字列 str_1 から生成できる異なる巡回置換(循環シフト)の集合「SET」を作成し、次に集合内の各要素とバイナリ文字列 str_2 とのXOR演算を実行して、その結果が0になるかどうかを確認します。XORが0になった場合はそのケースをカウントし、そうでない場合は無視します。

具体例で理解しましょう

例1

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

出力 − 他のバイナリ文字列とのXORが0となる巡回置換の個数: 4

説明 − str_1 = "1111" の巡回置換は4通り存在しますが、いずれも "1111" という同じ文字列です。各巡回置換と str_2 = "1111" のXORを計算すると {1111} ^ "1111" = 0 となり、すべてのケースで0が得られます。したがって出力は4になります。

例2

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

出力 − 他のバイナリ文字列とのXORが0となる巡回置換の個数: 1

説明 − str_1 から作成される巡回置換の集合は {1101, 1110, 1011, 0111} となります。次に、各要素と文字列 str_1 とのXOR演算を行います。

{1101} ^ 1101 = 0

{1110} ^ 1101 ≠ 0

{1011} ^ 1101 ≠ 0

{0111} ^ 1101 ≠ 0

XORが0になるのは1つだけであるため、カウントは1となります。

プログラムで使用しているアプローチ

• 2つのバイナリ文字列 str_1 と str_2 を入力として受け取り、さらなる処理のために関数 cyclic_permutation() に渡します。
• 一時的な操作として、まず str_2 を str_2 + str_2 で連結し、その後 str_2.substr(0, str_2.size()-1) で末尾の1文字を取り除きます。これにより、元の文字列のすべての巡回置換が1つの文字列内に含まれるようになります。
• 文字列型変数 str を作成し、str_1 と str_2 を区切り文字 "$" を挟んで連結します(str_1 + "$" + str_2)。この区切り文字により、パターンとテキストの境界が明確になり、誤ったマッチングを防げます。次に文字列 str の長さを計算し、その長さ分の整数型配列を作成します。
• 文字列 str と配列を引数として関数 check() を呼び出します。この関数はZ-algorithm(Z配列)を実装しており、各位置において文字列の先頭と何文字一致するかを線形時間 O(N) で効率的に計算します。
• check() 関数の内部では、以下の処理を行います。
  • 2つの変数 start と end を宣言し、0で初期化します。
  • 文字列の長さを計算します。
  • i を 1 から文字列長 - 1 までループさせます。i > end の場合は start = i、end = i と設定し、end が文字列長未満かつ str[end - start] == str[end] が成立する間、end を1ずつ増加させます。
  • arr[i] を end - start に設定し、その後 end を1減らします。
  • それ以外の場合は、一時変数 temp に i - start を設定します。arr[temp] < end - i + 1 であれば arr[i] に arr[temp] を代入します。そうでなければ、start を i に設定し直し、end が文字列長未満かつ str[end - start] == str[end] が成立する間 end を増加させて、arr[i] を end - start に設定した後、end を1減らします。
• i を 1 から文字列 str の長さ - 1 までループさせ、arr[i] が文字列 str_1 の長さと等しい場合、カウントを1増やします。これは、その位置から始まる巡回置換が str_1 と完全に一致すること(XORが0になること)を意味します。
• 最後にカウントを返します。
• 結果を出力します。

実装例

#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

この手法では、すべての巡回置換を個別に生成してXORを計算する代わりに、Z-algorithmを利用することで全体の計算量を O(N) に抑えることができ、非常に効率的です。