2020-03-12 刷题1（字符串公因子）

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的最大公约数的前缀，就是两个字符串的最大公因子。