题目链接：
题目描述：
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “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] 为大写英文字母
算法：
题目分为两个解题步骤：
第一步，我们需要判断S和T是否存在最大共因子。假设S和T存在最大公因子X，则有S=mX，T=nX。那么S+T=（m+n）X=T+S。反之，如果不存在最大公因子，则假设S=mX，T=nX'，则S+T=mX+nX'≠nX'+mX=T+S。
第二步，是求出最大公因子。通过第一步，我们已经知道S和T存在最大公因子X了，即S=mX，T=nX。假设S长度大于T，则我们有S-T=(m-n)X，同样是S和T的最大公因子。即S字符串从S[T.size()]到S[S.size()-1]的部分S'，同样可以除尽最大公因子。接着我们可以用较短的T和刚刚求出来的S’重复上述步骤，直到求出最大公因子。这个思路实际上是GCD（辗转相除法）在字符串领域的扩充。
事实上，我们只考虑字符串的长度。假设S的长度为m，T的长度为n，那么如果S和T存在最大公因子，那么最大公因子的长度一定是m和n的长度。因此我们可以直接求出m和n的最大公因数k，并且取S的最前面k个数进行返回。
代码：
// 处理字符串
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);
}
};
