字符串的最大公因子

题目：
对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例：
示例 1：

输入：str1 = “ABCABC”, str2 = “ABC”
输出：“ABC”

示例 2：

输入：str1 = “ABABAB”, str2 = “ABAB”
输出：“AB”

示例 3：

输入：str1 = “LEET”, str2 = “CODE”
输出：""

思想1： 穷举法：列举所有的可能，进行判断找出最大公因子。

• 我们从str1,str2两个字符串中选取最短的进行循环，长度不断递减，因为为公因子，所以它的长度一定是str1和str2长度的公因子，所以
  len1%k = =0 &&len2%k= =0, 满足这个条件进行字符串不断调用验证。
• 写一个验证函数，验证传来的字符串是否为s的子串，就看他是否可以通过不断连接构成s。
• 我们来举个例子，如下图所示：
  
  根据上面的思路我们就可以写出代码：
  代码1：

bool check(string s,string t)
{
	int count=t.length()/s.length();//需要拼接的次数
	string temp="";
	for(int i=0;i<count;i++)
	{
		temp+=s;//字符串进行连接
		if(temp==t)
		{
			return true;
		}
	}
	return false;

}
string gcdOfStrings(string str1, string str2) 
{
	int len1=str1.length();
	int len2=str2.length();
	int len=min(len1,len2);
	for(len;len>0;len--)
	{
		if(len1%len==0&&len2%len==0)
		{
			string s=str1.substr(0,len);
			if(check(s,str1)&&check(s,str2))//检验
			{
				return s;
			}
		}
	}
	return "";	
}

思路2：看了第一种解题思路的同学肯定可以想到什么：那就是求最大公约数。我们找的len不就是len1和len2的最大公约数吗，那么我们可以化简上述代码

• 循环求解len长度变为用欧几里得公式求公约数，C++的 < algorithm>有个自带的gcd函数：__gcd(len1,len2)，但需要C++17才支持，所以在这我们自己写一个就好。
• 其他的不变。
  代码2：

bool check(string s,string t)
{
	int count=t.length()/s.length();
	string temp="";
	for(int i=0;i<count;i++)
	{
		temp+=s;
		if(temp==t)
		{
			return true;
		}
	}
	return false;
}
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
//引入欧几里得公式求最大公约数，然后检验即可
string gcdOfStrings1(string str1, string str2) 
{
	int len1=str1.length();
	int len2=str2.length();
	int len=min(len1,len2);
	string s=str1.substr(0, gcd(len1,len2));//c++17才支持
	if(check(s,str1)&&check(s,str2))
	{
				return s;
	}
	return "";	
}

思想3：一种数学思维来解决

• 我们仔细想一下如果str1由m个s拼接成，str2由n个s拼接成，那么（m+n)个s和（n+m)个s应该是相等的，即str1+str2==str2+str1,如下图：
  
  否则str1和str2根本不会存在最大公因子。

• 那么我们就可以根据欧几里得公式直接求出最优解，len=gcd(len1,len2)，直接输出substr(str1,len）即可，它就是最优解。

• 为什么我们不用验证了，因为我们已经可以确定他肯定由最优解。
  代码3：

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
string gcdOfStrings2(string str1, string str2) 
{
	if(str1+str2!=str2+str1) return "";
	return str1.substr(0,gcd(str1.length(),str2.length()));
}

我最开始一种也没想到????，慢慢学习吧！加油????。