给定两个字符串 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