今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
另一个python示例(基于答案):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
其他回答
另一个基于答案的Ruby解决方案:
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
这是一个O(n) and in place算法。它对字符串的元素使用<操作符。当然不是我的。我把它从这里(网站是波兰语。我以前偶然发现过一次，现在在英语中找不到这样的东西，所以我展示了我拥有的:))。
bool equiv_cyc(const string &u, const string &v)
{
int n = u.length(), i = -1, j = -1, k;
if (n != v.length()) return false;
while( i<n-1 && j<n-1 )
{
k = 1;
while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
if (k>n) return true;
if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
}
return false;
}
int rotation(char *s1,char *s2)
{
int i,j,k,p=0,n;
n=strlen(s1);
k=strlen(s2);
if (n!=k)
return 0;
for (i=0;i<n;i++)
{
if (s1[0]==s2[i])
{
for (j=i,k=0;k<n;k++,j++)
{
if (s1[k]==s2[j])
p++;
if (j==n-1)
j=0;
}
}
}
if (n==p+1)
return 1;
else
return 0;
}
现在来点完全不同的东西。
如果你想在一些约束条件下快速得到答案当字符串不是相互旋转时
在两个字符串上计算一些基于字符的校验和(比如xoring所有字符)。如果签名不同，字符串不是彼此的旋转。
同意，它可能会失败，但如果字符串不匹配，它会很快说，如果它们匹配，你仍然可以使用另一种算法，比如字符串连接来检查。
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
