C++で指定された文字列の最大公約数の数を数えます

入力として2つの文字列numoとdemoが与えられます。目標は、両方の文字列の共通除数の数を見つけることです。文字列の除数は、次の手法を使用して検出されます。文字列strの除数がsub1の場合、strが生成されるまで何度でも繰り返すことで、sub1を使用してstrを作成できます。例：str =abcabcabc sub1 =abc

例

入力

numo = "abababab" demo = "abababababababab"

出力

Count of number of common divisors of the given strings are: 2

説明

The strings can be generated using following divisor substrings :
“ab”, “abab”

入力

numo = "pqqppqqp" demo = "pqpq"

出力

Count of number of common divisors of the given strings are: 0

説明

The strings do not have any common divisor. Only divisors of both are:
“pqqp” for numo and “pq” for demo.

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

文字列sub1がstrの約数になるには、strの接頭辞である必要があり、その長さはstrの長さを完全に分割する必要があります。文字列numoとdemoの両方を使用して、sub1のこの状態を確認し、それに応じてカウントをインクリメントします。

• 文字列numoとdemoを入力として受け取ります。

• 関数verify（string str、int val）は、文字列strを受け取り、0からvalまでのサブ文字列を繰り返してstrを生成できる場合は、1を返します。

• 関数common_divisor（string numo、string demo）は両方の文字列を受け取り、指定された文字列の最大公約数の数を返します。

• 初期カウントを0とします。

• 入力文字列の長さを計算します。そして、最小の長さをmin_valに格納します。

• forループを使用してインデックスi=0からmin_valまでトラバースします。

• サブストリングの現在の長さiが両方のストリングの長さを除算する場合、numo_sizeとdemo_sizeおよびプレフィックスもnumo.substr（0、i）==demo.substr（0、i）と一致します。

• 次に、verify（）を使用して、サブストリング0からiがnumoとdemoの両方の約数であるかどうかを確認します

• verify（numo、i）とverify（demo、i）の両方が1を返す場合は、カウントをインクリメントします。

• forループの最後に、結果としてカウントが返されます。

例

#include <bits/stdc++.h>
using namespace std;
int verify(string str, int val){
   int length = str.length();
   for (int i = 0; i < length; i++){
      if(str[i] != str[i % val]){
         return 0;
      }
   }
   return 1;
}
int common_divisor(string numo, string demo){
   int count = 0;
   int numo_size = numo.size();
   int demo_size = demo.size();
   int min_val = min(numo_size, demo_size);
   for(int i = 1; i <= min_val; i++){
      if(numo_size % i == 0){
         if(demo_size % i == 0){
            if(numo.substr(0, i) == demo.substr(0, i)){
               if(verify(numo, i)==1){
                  if(verify(demo, i)==1){
                     count++;
                  }
               }
            }
         }
      }
   }
   return count;
}
int main(){
   string numo = "abababab";
   string demo = "abababababababab";
   cout<<"Count the number of common divisors of the given strings are:
   "<<common_divisor(numo, demo);
   return 0;
}

出力

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

Count the number of common divisors of the given strings are: 3