由字串A重複x次和字串B重複y次連線形成的最短字串，滿足n(A)*x = n(B)*y

---

在這個問題中，我們需要找到最短的字串，它是字串A和字串B的倍數。這個問題非常類似於尋找兩個數字的最小公倍數(LCM)。我們可以找到兩個字串長度的最小公倍數，透過自身連線使兩個字串的長度等於最小公倍數。之後，我們可以比較字串，檢查是否可以得到最短的字串，它是A和B的倍數。

問題陳述 – 我們給定不同長度的字串A和字串B。我們需要找到最短的字串，它是字串A和字串B的倍數。

注意 – 如果可以透過將第一個字串自身連線多次來獲得第二個字串，則第一個字串是第二個字串的倍數。

示例

輸入

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

輸出

‘ddd’

解釋 – 字串“ddd”是A的倍數，也是B的倍數，因為1*A = 3*B。

輸入

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

輸出

-1

解釋 – 因為兩個字串不同，所以無法找到最短的字串，它是A和B的倍數。

輸入

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

輸出

‘abcabcabcabcabcabc’

解釋 – 輸出顯示，最短的字串是A和B的倍數，因為2*A == 3*B。

方法一

這種方法將找到兩個字串長度的最大公約數(GCD)。之後，我們將使用GCD找到最小公倍數(LCM)。根據LCM值，我們將把兩個字串自身連線多次，並匹配最終字串以檢查它們是否相等。

演算法

步驟1 – 定義getGCD()函式來查詢兩個數字的最大公約數，它以第一個和第二個作為引數。

步驟1.1 – 如果第一個等於零，則返回第二個。

步驟1.2 – 獲取第二個對第一個的模，並將其作為GCD函式的第一個引數，同時進行遞迴呼叫。

步驟2 – 在multipleOfAandB()函式中，用字串A和字串B的長度初始化len1和len2變數。

步驟3 – 執行getGCD()函式以獲得兩個數字的最大公約數，並將其儲存在gcd變數中。

步驟4 – 接下來，將len1和len2相乘，然後除以GCD值以獲得LCM值。

步驟5 – 初始化兩個名為temp1和temp2的臨時字串，用於儲存相乘後的字串。

步驟6 – 將字串A追加到temp1，重複LCM/len1次。

步驟7 – 將字串B追加到temp2，重複LCM/len2次。

步驟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;
}

輸出

The resultnat string is - ddd

時間複雜度 – O(log(N*M))，因為我們找到了長度的GCD並連線了字串

空間複雜度 – O(N + M)，因為我們需要儲存最短字串。

這個問題的解決方案與尋找兩個數字的最小公倍數非常相似，但是我們需要確保在這裡，字串在多次連線後應該是相同的。