LeetCode 1071. 字符串的最大公因子（字符串的最大公约数）

示例 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] 为大写英文字母

class Solution {
public:
    string gcdOfStrings(string s1, string s2) {
        while(s1 != s2)
        {
        	if(s1.size() > s2.size())
        		swap(s1,s2);//保证s2长
        	if(s2.find(s1) != 0)//首位必须一样，对齐
        		return "";
        	s2 = s2.substr(s1.size());//在s2找到了s1，把s2前面的s1部分砍掉
        }
        return s1;
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if(str1+str2 != str2+str1)//充分必要条件
            return "";
        return str1.substr(0,__gcd(str1.size(),str2.size()));//c++内置gcd
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if(str1+str2 != str2+str1)
            return "";
        return str1.substr(0,gcd(str1.size(),str2.size()));
    }

    int gcd(int a, int b)
    {	//求最大公约数
        int r;
        while(b)
        {
            r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
};