计算 C++ 中给定字符串的公约数的个数

2023-06-21 12:55:03 71

给定两个字符串numo和demo作为输入。目标是找到两个字符串的公约数。使用以下技术找到字符串的除数：如果字符串str将sub1作为它的除数，那么我们可以使用sub1构造str，通过重复任意次数直到str生成为止。示例：str=abcabcabcsub1=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(stringstr,intval)接受字符串str，如果0到val之间的子字符串可以重复生成str，则返回1。

函数common_divisor(stringnumo,stringdemo)接受两个字符串并返回给定字符串的公约数的计数。

取初始计数为0。

计算输入字符串的长度。并将最小长度存储在min_val中。

使用for循环从索引i=0遍历到min_val。

如果子串的当前长度i除以字符串numo_size和demo_size的长度，并且前缀也匹配numo.substr(0,i)==demo.substr(0,i)。

然后使用以下命令查找子串0到i是否是numo和demo的除数verify()

如果两个verify(numo,i)并verify(demo,i)返回1，则增量次数。

在for循环结束时返回计数作为结果。

示例

#include 
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:
   "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count the number of common divisors of the given strings are: 3

计算 C++ 中给定字符串的公约数的个数

输入

解释

输入

解释

示例

热门推荐

随机推荐