今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
C#:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
其他回答
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
另一个python示例(基于答案):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
连接string1和string2，使用KMP算法检查string2是否出现在新形成的字符串中。因为KMP的时间复杂度小于substr。
由于其他人已经提交了二次最坏情况时间复杂度解决方案，我将添加一个线性解决方案(基于KMP算法):
bool is_rotation(const string& str1, const string& str2)
{
if(str1.size()!=str2.size())
return false;
vector<size_t> prefixes(str1.size(), 0);
for(size_t i=1, j=0; i<str1.size(); i++) {
while(j>0 && str1[i]!=str1[j])
j=prefixes[j-1];
if(str1[i]==str1[j]) j++;
prefixes[i]=j;
}
size_t i=0, j=0;
for(; i<str2.size(); i++) {
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
for(i=0; i<str2.size(); i++) {
if(j>=str1.size()) return true;
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
return false;
}
工作示例
使用strlen和strpos函数在PHP中很容易编写:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
我不知道strpos内部使用什么，但如果它使用KMP，它将在时间上是线性的。
