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

  • Z时代
  • 2024-01-10
  • 分类：综合

给定两个字符串 numo 和 demo 作为输入。目标是找到两个字符串的公约数。使用以下技术找到字符串的除数：如果字符串 str 将 sub1 作为它的除数，那么我们可以使用 sub1 构造 str ，通过重复任意次数直到 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)。

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

  • 如果两个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

以上是 计算 C++ 中给定字符串的公约数的个数 的全部内容， 来源链接： utcz.com/z/350520.html

回到顶部