问题：（该问题转自《Algorithms（FourthEdition）》网站）
给定两个字符串x、y，设计一个算法来判断是否存在一对正整数m、n，使得x^m = y^n。这里x^m表示m个x相连接所形成的字符串。
在给出分析和解决方案之前我们先做一些约定：
1. 所有讨论都是在所涉及数据为正整数的前提下进行。
2. lcm(X, Y)：整数X和Y的最小公倍数
gcd(X,Y)：整数X和Y的最大公约数
3. 如果gcd(X, Y) = 1，则X和Y互质，不对X或Y等于1的情况进行区分。
分析：
如果确实存在满足要求的整数对，那么很明显，字符串x和y必然具有某些共性。因为x^m和y^n分别是由若干个x和若干个y连接而成，故可以知道一个字符串的开始部分必然与另一个字符串相同，且结束部分也必然与另一个字符串相同。更具体地说，对于y^n这个串，我们知道其首部是一个x，我们把这个x去掉，之后的首部还是一个x，而且这个过程可以一直做下去，直到串y^n用完。
由以上分析可以很容易地设计出以下算法：
算法一：
构造字符串x^m，其中m =lcm(|x|,|y|) / |x|，再构造字符串y^n，其中n = lcm(|x|,|y|) / |y|，然后检查二者是否相同。或是更简单的办法，构造完x^m后，检查它是否是若干个y的连接。
这个算法非常简单，可以算做是一种Brute-Force方法，并且利用了最小公倍数和整数的性质减少了运算。但这个算法可能需要很大的时空开销，而且当最小公倍数溢出时，也需要更复杂的处理。当然，也可以不去构造字符串x^m，直接在x上循环搜索y，直到二者同时到达结尾。这样额外的空间开销降为了O(1)。但运行时间并没有降低，最坏情况下，时间复杂度为O(lcm(|x|, |y|))。而lcm可能会很大，有时会接近|x|*|y|。
为了寻求更高效的方法，我们需要深入分析x和y的共性。假定存在m、n，使得x^m = y^n，那么我们很容易想到x和y必定是某一公共部分的重复串联，比如：x = abab，y = ababab，那么公共部分就是ab。
如果这个猜想成立的话，那么似乎就会有更简单的方法。
算法二：
检查x和y是否是某个公共部分的重复。
但可惜的是这个解法并没那么容易。因为确定我们要找的公共部分可能需要很复杂的算法。这里有一个捷径：如果猜想成立的话，那么由整除的性质可知，公共部分的长度应该是gcd(|x|, |y|)或gcd(|x|, |y|)的约数。不管是哪种，gcd(|x|, |y|)一定是可以的。因此，我们可以直接检查x和y是否是同一个长为gcd(|x|, |y|)的字符串的重复。算法非常简单，时间复杂度是O(log(min{|x|, |y|}) + |x|+|y|) = O(|x| + |y|)。其中，对数项是求最大公约数的复杂度，这里不对数学运算和字符比较的花费做区分。
另外，这个算法需要证明之前的那个命题，即：“存在m、n，使得x^m = y^n”等价于“x和y是某一公共部分的重复串联”。
那有没有更好的方法呢？答案是肯定的，只需要检查xy是否等于yx即可。
这个证明有些复杂，我们考虑以下三个命题：
（1）存在m、n，使得x^m = y^n。
（2）x和y是某一公共部分的重复串联，且该公共部分的长度应该是gcd(|x|, |y|)。
（3）xy = yx。
下面我们要做的就是证明这三个命题等价，为此，只需要证明这三个命题可以循环导出即可。
<1> （2）→（3）
显然成立。
<2> （1）→（2）
(i) 若|x| = |y|，显然成立。
(ii) 若|x| != |y|，不失一般性，设|x| <|y|。
引理a：若正整数x和y互质，则0 mod y,x mod y,2*x mod y, ..., (y-1)*x mod y必然取遍0,1,...,y-1。
证：
①若其中有一个数为2，则显然成立。
因为另一个数必为奇数，记为2*k+1，则
若x = 2，则按命题中取模顺序会得到2, 4, 6, ..., 2*k, 1, 3, 5, ..., 2*k-1；
若y = 2，则会得到1, 0。
因此，命题成立。
②若x和y都不为2。则二者均为奇数。
由同余的性质，在不考虑顺序的前提下，0 mod y, x mod y, 2*x mod y, ..., (y-1)*x mod y 和0/2*x mod y, 2/2*x mod y, ..., (y-1)/2*x mod y, (y+1)/2*x mod y, ..., (y+y-2)/2*x mod y的结果是一样的。
下面证这些结果是互不相同的。
考虑(y-m)/2*x mod y和(y-n)/2*x mod y，其中m,n =y, y-2, y-4, ..., 3, 1, -1, -3, ..., 4-y, 2-y，且m != n。
反证法：假设它们的结果是相同的。
那么，[(y-m)/2*x - (y-n)/2*x] mod y = 0。即：(n-m)/2*x mod y =0。
由于x和y互质，那么2*y必然整除n-m。从而n-m >= 2*y。而n-m <= y - (2-y) = 2*y - 2，产生矛盾，故假设不成立。因此任意两项的结果都是不同的。
从而引理得证。
回到(ii)的证明。
不妨令m、n互质（因为我们总可以通过约分而做到），则必有
m = lcm(|x|, |y|) / |x|， n =lcm(|x|, |y|) / |y|。
取x' = |x| / gcd(|x|, |y|)，y' = |y| / gcd(|x|,|y|)，
则x'和y'互质（整数唯一分解定理的推论）。
并且由于m*x' = n *y'，故m = y', n = x'。
那么由引理a，可知x' mod y', 2*x' mod y', ..., (m-1)*x mod y'必然取遍0,1,...,y'-1。
则|x| mod |y|, 2*|x| mod |y|, ..., (m-1)*|x| mod |y|必然取遍0, gcd,..., |y|-gcd。
对应到字符串x和y中就是，x的长为gcd=gcd(|x|, |y|)的前缀与y串的所有(0, gcd), (gcd, 2*gcd), ..., (|y|-gcd, |y|)子串均相同。因此，y串是由x的长为gcd的前缀串联而成。而由于x是y的前缀，因此，x也是由该串串联而成。由此原命题成立。
综合(i), (ii)，（1）→（2）得证。
<3> （3）→（1）
不失一般性，设|x| <= |y|。
(i) 若|x|整除|y|，即|y|是|x|的倍数，显然成立。因为此时可以看出y就是由若干个x串接而成的。
(ii) 若|x|不能整除|y|，则有|y| = k*|x|+ c，其中k和c都是正整数，且0 < c < |x|。
考虑下图：
1区 = x → 2区 = x（xy = yx）
→ 3区 = x（2区和3区对应y的同一区段）
→4区 = x
→...
→a区 = x
→b区 = x
→c区 = c（一个长为c的字符串）
→d区 = c
从而有xc = cx ①
另外，由于|y| = k*|x| + |c|，因此有
x^|y| = x^( k*|x| + |c|) = x^(k*|x|) * x^|c| ②
y^|x| = (c*x^k)^|x| = c^|x| * x^(k*|x|) ③
①用于③得到：
y^|x| = x^(k*|x|) * c^|x| ④
欲证命题（1）成立，只需要证x^|y| = y^|x|，
由②和④，可知，这等价于证x^|c| = c^|x|。
记命题（1）x^m = y^n为f(|x|, |y|)，则上述等价关系表明这个问题可以通过证f(|x|, |c|) = f(|x|, |y| mod |x|)来解决（f(a, b)表示存在正整数对m,n，使得m个y的长为a的前缀串联与n个x的长为b的前缀串联相同）。
根据欧几里得辗转相除法可知，不断这样递归下去，最终一定会到达一个参数是另一个参数的整数倍的状态，而此时，由<3>.(i)可知是成立的。
综合(i), (ii)，（3）→（1）得证。
综合<1>, <2>,<3>，可知命题（1）、（2）、（3）互为等价。
有了（1）和（2）的等价性，算法二就得到了证明。而有了它们与命题（3）的等价性，我们可以设计一种更加高效和优雅的算法。
算法三：
直接检测xy和yx是否相同即可。
相比算法二，这里省去了求最大公约数的部分。此外，算法三和算法二都需要对x和y中的每个字符访问两次。可能有人会问算法二为什么是访问两次，那是因为需要有一个额外的指针来扫描它们的公共部分，直到x和y都扫描完毕。对于算法三，最高效的方法当然是用两个指针来扫描字符串，一个先扫描x再扫描y，与此同时另一个先扫描y再扫描x。如果字符串较短，则在Java中更是仅需要一行代码就能搞定。该算法的时间复杂度为O(|x|+|y|)。