1071. Greatest Common Divisor of Strings

GCD思想

我们学过求最大公约数的函数GCD，本题这是利用此方法进行求解。对于两个字符串，我们要求它们的最大公共重复字串，本质上就是在求两个正整数的最大公约数的问题。与更相减损术一样，两字符串长度不一，检测长的字符串的prefix与短的字符串是否相同，若不同，则无公共字串，然后用长的字符串去掉prefix，再将两字符串送入GCD函数，直到两个字符串完全一样。

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