1071 字符串的最大公因子
标签：字符串，公约数
解法一：类似于最大公因数的更相减损法，两个数num1，num2（假设num1>=num2)，两个数相等，则最大公因数就是它们自己，否则，num1和num2的最大公因数就等于num2和num1-num2的最大公因数。依次递归下去，直到两个数相等，就找到了最大公因数。
迁移到字符串上，如果两个字符串相同，则最大公因子就是它们自己，否则，最大公因子就是短串和长串减短串的最大公因子。依次递归，直到两个串完全相同。
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
// boundary
if(str1.size() == str2.size()){
if(str1 == str2) return str1;
return "";
}
string strl, strs;
if(str1.size() > str2.size()){
strl = str1;
strs = str2;
}
else{
strl = str2;
strs = str1;
}
if(strl.find(strs) != 0) return "";
string sub = strl.substr(strs.size());
return gcdOfStrings(strs, sub);
}
};
解法二：数学法
如果两个字符串str1和str2，str1+str2=str2+str1，也就是两种拼法，得到的结果一样，那他们一定有公因子；得到结果不相等，就一定没有公因子。最大公因子的长度就是它们长度的最大公约数。所以，如果存在公因子，求取长度为最大公约数的前缀即可。
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if(str1 + str2 != str2 + str1) return "";
return str1.substr(0, __gcd(str1.size(), str2.size()));
}
};
证明的话，两种情况，一种情况下，短的字符串的长度是长字符串的长度的因数，这种情况下，短字符串就是公因子；另一种情况，短字符串的长度不是长字符串的长度的因数，通过交换两个字符串的位置，长字符串的长度为(l1-l2)的前缀与长度为l1-l2的后缀相同；长度为l2的前缀与l2的后缀相同。所以长度为l2和l1-l2的最大公约数的前缀，就是两个字符串的最大公因子。
