題目鏈接：
題目描述：
對于字符串 S 和 T系奉，只有在 S = T + ... + T（T 與自身連接 1 次或多次）時(shí)矮瘟，我們才認(rèn)定 “T 能除盡 S”。
返回最長字符串 X饭望，要求滿足 X 能除盡 str1 且 X 能除盡 str2仗哨。
- 示例 1：
輸入：str1 = "ABCABC", str2 = "ABC"
輸出："ABC" - 示例 2：
輸入：str1 = "ABABAB", str2 = "ABAB"
輸出："AB" - 示例 3：
輸入：str1 = "LEET", str2 = "CODE"
輸出：""
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 為大寫英文字母
算法：
題目分為兩個(gè)解題步驟：
第一步形庭，我們需要判斷S和T是否存在最大共因子。假設(shè)S和T存在最大公因子X厌漂，則有S=mX萨醒，T=nX。那么S+T=（m+n）X=T+S苇倡。反之富纸，如果不存在最大公因子，則假設(shè)S=mX旨椒，T=nX'晓褪，則S+T=mX+nX'≠nX'+mX=T+S。
第二步综慎，是求出最大公因子涣仿。通過第一步，我們已經(jīng)知道S和T存在最大公因子X了示惊，即S=mX变过，T=nX。假設(shè)S長度大于T涝涤，則我們有S-T=(m-n)X媚狰，同樣是S和T的最大公因子。即S字符串從S[T.size()]到S[S.size()-1]的部分S'阔拳，同樣可以除盡最大公因子崭孤。接著我們可以用較短的T和剛剛求出來的S’重復(fù)上述步驟，直到求出最大公因子糊肠。這個(gè)思路實(shí)際上是GCD（輾轉(zhuǎn)相除法）在字符串領(lǐng)域的擴(kuò)充辨宠。
事實(shí)上，我們只考慮字符串的長度货裹。假設(shè)S的長度為m嗤形，T的長度為n，那么如果S和T存在最大公因子弧圆，那么最大公因子的長度一定是m和n的長度赋兵。因此我們可以直接求出m和n的最大公因數(shù)k，并且取S的最前面k個(gè)數(shù)進(jìn)行返回搔预。
代碼：
// 處理字符串
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1 + str2 != str2 + str1) return "";
if (str1 == str2)
return str1;
else if (str1.size() < str2.size())
return gcdOfStrings(str1, str2.substr(str1.size()));
else
return gcdOfStrings(str2, str1.substr(str2.size()));
}
};
// 處理字符串長度
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1 + str2 != str2 + str1) return "";
return str1.substr(0, gcd(str1.size(), str2.size()));
}
private:
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
};
