题目

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

首先假设这两个字符串都是由一个(且最长)子串X生成的，那么很容易想到S串和T串都是X的重复，则S=k个X，T=n个X，则S+T == T+S == (k+n)个X
则如果S+T == T+S，则有解，否则直接返回空串表示无解。

然后S和T都是X的倍数，则最长X为他们长度的最大公因子（题目都写了）

代码

public class Solution {
  public String gcdOfStrings(String str1, String str2) {
      if ((str1+str2).equals(str2+str1))
          return str1.substring(0,GCD(str1.length(),str2.length()));
      else
          return "";
  }
  public int GCD(int a,int b)
  {
      if(a==0) return b;
      if(b==0) return a;
      if(!(a%2==1)&&!(b%2==1))
      {
          return GCD(a>>1,b>>1)<<1;
      }
      else if(!(b%2==1))
      {
          return GCD(a,b>>1);
      }
      else if(!(a%2==1))
      {
          return GCD(a>>1,b);
      }
      else
      {
          return GCD(Math.abs(a-b),Math.min(a,b));
      }
  }
}

版权声明：本文为JethroYu原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/JethroYu/p/12467001.html