C++ 由字符串A出现x次和字符串B出现y次形成的最短字符串，条件是n(A)\x = n(B)*y

在这个问题中，我们需要找到最短的字符串，它是字符串A和字符串B的倍数。这个问题与找到两个数字的最小公倍数（LCM）非常相似。我们可以找到两个字符串长度的LCM，并通过将其连接到自身来使两个字符串的长度等于LCM。之后，我们可以比较字符串，以检查是否有可能得到字符串A和B的倍数的最短字符串。

问题陈述 - 我们给定了长度不同的字符串A和字符串B。我们需要找到最短的字符串，它是字符串A和字符串B的倍数。

注意 - 如果我们可以通过将第一个字符串多次连接到自身来实现第二个字符串，则第一个字符串是第二个字符串的倍数。

示例示例

输入

A = "ddd", B = "d";

输出

‘ddd’

解释 - “ddd”字符串是A的倍数，也是B的倍数，因为1A = 3B。

输入：

A = "abc", B = "def";

输出

-1

解释 - 不可能找到一个同时是A和B的倍数的最短字符串，因为这两个字符串是不同的。

输入

A = "abcabcabc", B = "abcabc";

输出

‘abcabcabcabcabcabc’

解释 – 输出结果中显示出短字符串是A和B的倍数，即2A 3B。

方法 1

这个方法将找到这两个字符串长度的最大公约数（GCD）。然后，我们将使用最大公约数来计算最小公倍数（LCM）。根据LCM的值，我们将把两个字符串重复连接多次，并比较最终字符串来检查它们是否相等。

算法

Step 1 – 定义一个getGCD()函数，用于找到两个数的最大公约数，该函数接受第一个和第二个数作为参数。

Step 1.1 – 如果第一个数等于零，返回第二个数。

Step 1.2 – 在进行递归调用时，将第二个数与第一个数取模后的结果作为GCD函数的第一个参数。

Step 2 – 在multipleOfAandB()函数中，使用字符串A和字符串B的长度初始化len1和len2变量。

Step 3 – 执行getGCD()函数获取两个数的最大公约数，并将其存储在gcd变量中。

Step 4 – 接下来，将len1和len2相乘，并将结果除以GCD的值，得到LCM的值。

Step 5 – 初始化两个临时字符串temp1和temp2以存储重复连接的字符串。

Step 6 – 将字符串A重复连接LCM/len1次，并将结果存储在temp1中。

Step 7 – 将字符串B重复连接LCM/len2次，并将结果存储在temp2中。

Step 8 – 如果temp1和temp2相等，则输出temp1或temp2的值。否则，输出-1。

示例

#include <bits/stdc++.h>
using namespace std;

// Get GCD of numbers
int getGCD(int first, int second){
    if (first == 0) {
        return second;
    }
    return getGCD(second % first, first);
}
void multipleOfAandB(string A, string B){
    int len1 = A.length();
    int len2 = B.length();
    int gcd = getGCD(len1, len2);
    // Get LCM of len1 and len2
    int lcm = (len1 * len2) / gcd;
    // To store multiple of A
    string temp1 = "";
    // To store multiple of B
    string temp2 = "";
    // string concatenation
    for (int m = 0; m < (lcm / len1); m++) {
        temp1 = temp1 + A;
    }
    // string concatenation
    for (int m = 0; m < (lcm / len2); m++) {
        temp2 = temp2 + B;
    }
    // Compare temp1 and temp2
    if (temp1 == temp2) {
        cout << "The resultnat string is - " << temp1;
    } else {
        cout << -1;
    }
}
int main() {
    string A = "ddd";
    string B = "d";
    multipleOfAandB(A, B);
    return 0;
}