大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

字符串处理，最大公约数

题目解答方法的文字分析

题目要求找出一个最长的子串，这个子串既可以生成牛A的名字str1，也可以生成牛B的名字str2。这就意味着这个子串必须是str1和str2的公约串。

思路：

  1. 首先，如果str1和str2的长度为0，那么它们不可能有公约串，直接返回空串。
  2. 其次，如果str1和str2相等，那么它们的公约串就是str1（或str2，因为两个相等）本身，直接返回str1即可。
  3. 现在考虑str1和str2长度不相等的情况，首先求出str1和str2的长度的最大公约数（GCD）gcd，如果str1和str2的长度没有公约数，那么它们不可能有公约串，直接返回空串。否则，我们取str1的前gcd个字符作为可能的公约串，然后判断这个子串是否满足条件，即是否能够重复构成str1和str2。
  4. 遍历str1和str2，检查它们是否都能由这个可能的公约串重复若干次构成，如果是，则返回这个子串，否则继续尝试更短的子串。

举例说明：假设str1="ABABAB"，str2="ABAB".

  1. 首先，求出str1和str2的长度的最大公约数gcd=2。
  2. 取str1的前gcd个字符，即"AB"，我们需要检查str1和str2是否都能由"AB"重复若干次构成。
  3. 对于str1，str1的长度是6，而"AB"重复2次构成"ABAB"，长度也是6，满足条件。
  4. 对于str2，str2的长度是4，而"AB"重复1次构成"AB"，长度也是4，满足条件。
  5. 因此，"AB"是str1和str2的公约串，且为最长公约串。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <string>
using namespace std;

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        int gcd = GCD(len1, len2); // 求str1和str2长度的最大公约数

        string candidate = str1.substr(0, gcd); // 取str1的前gcd个字符作为可能的公约串

        // 检查str1是否由candidate重复若干次构成
        for (int i = 0; i < len1; i += gcd) {
            if (str1.substr(i, gcd) != candidate) {
                return "";
            }
        }

        // 检查str2是否由candidate重复若干次构成
        for (int i = 0; i < len2; i += gcd) {
            if (str2.substr(i, gcd) != candidate) {
                return "";
            }
        }

        return candidate;
    }

private:
    // 辗转相除法求最大公约数
    int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
};

关于这道题目的题解就是这样了，希望对大家有所帮助！ 记得给阿Q点赞、收藏、关注，三连支持阿Q！