数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 统计给定字符串的公因数个数
给定两个字符串 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 并返回 1，如果从 0 到 val 的子字符串可以重复生成 str。
函数 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
更新于: 2021年1月5日
224 次查看
广告