我的朋友在软件开发职位的面试中被问到以下问题：
给定两个字符串 s1 和 s2，你将如何检查 s1 是否是 旋转 版本的 s2？
例如：
如果 s1 = "stackoverflow"，则以下是它的一些旋转版本：
"tackoverflows"
"ackoverflowst"
"overflowstack"
而 "stackoverflwo" 不是旋转版本。
他给出的答案是：
取
s2并查找最长的前缀，它是s1的子字符串，这将给你旋转点。一旦找到该点，请在该点处断开s2，以获得s2a和s2b，然后只需检查concatenate(s2a,s2b) == s1是否成立。
对我和我的朋友来说，这看起来像一个很好的解决方案。 但面试官并不这么认为。 他要求提供更简单的解决方案。 请帮我说明如何用 Java/C/C++ 实现此功能？
感谢您提前的帮助。
首先确保s1和s2具有相同的长度。然后检查s2是否是s1连接s1后得到的子字符串：
algorithm checkRotation(string s1, string s2)
if( len(s1) != len(s2))
return false
if( substring(s2,concat(s1,s1))
return true
return false
end
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
(s1 + s1).contains(s2)。 - polygenelubricantss1+s1。显然，所有长度为s1.length的子字符串都是通过构造从s1旋转来的。因此，在s1+s1中作为子字符串并且长度为s1.length的任何字符串必须是s1的旋转。 - Daniel C. Sobral毋庸置疑地，更好的答案应该是：“好吧，我会向stackoverflow社区提问，并且在5分钟内可能会得到至少4个非常好的答案”。大脑很棒，但我更看重那些知道如何与他人合作解决问题的人。
另一个基于THE答案的Python示例：
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
s2而不是s1...然后意识到关系无论如何都是对称的。 - Matthieu M.def isrotation(s1, s2):
return len(s1)==len(s2) and re.compile(re.escape(s1)).search(2*s2) is not None - Duncanin 运算符不使用 O(n) 算法吗？ - Ken Blooma in b，其中 a 是 xxxxxxz，而 b 则是很多 x ：在最好的情况下，Python 将比较 len(b)-len(a) 个起始位置（我不确定这里，它可能只做 len(b) 次比较）和每个位置来自 len(a)-1 个字符的比较。另一方面，在带有常量前缀的正则表达式中，进行更少的比较（难以计算，但显然是 O(n)，通常比较少）。 - Duncans1 in s2已经被优化了。请参见http://effbot.org/zone/stringlib.htm以获取算法的描述。谷歌似乎表明Java没有快速的字符串搜索（例如，请参见http://johannburkard.de/software/stringsearch/），尽管我怀疑如果他们改变了它，它是否会破坏任何东西。 - Duncan其他人已经提交了二次方最坏时间复杂度的解决方案，我会添加一个线性的解决方案（基于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;
}
编辑：如果你发现了更为优雅和高效的方式，请参考其他回答。我会采用一种暴力的方式。首先检查字符串长度，然后尝试每一个可能的旋转偏移量。如果没有一个可行的解决方案，则返回false-如果有一个可行的解决方案，则立即返回true。
没有特别需要连接字符串 - 只需使用指针（C语言）或索引（Java）并同时遍历两个字符串，一个是第一个字符串的开头，另一个是第二个字符串的当前候选旋转偏移量，并在必要时进行包装。在每个字符串位置处检查字符是否相等。如果到达第一个字符串的结尾，则完成。
这也可以很容易地通过连接来实现——至少在Java中效率可能会稍低些。
这是一个只是为了好玩而使用正则表达式的示例:
boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
如果您可以使用一个特殊的分隔符，确保该字符不在任何字符串中出现，那么您可以使它更简单。
boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
你还可以使用有限重复的回顾后发：
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
哇，为什么大家对一个 O(n^2) 的答案感到如此兴奋呢？我相信我们可以做得更好。上面的答案包括在 O(n) 循环中进行的 O(n) 操作（子字符串 / indexOf 调用）。即使使用更高效的搜索算法，如 Boyer-Moore 或 KMP，最坏情况下还是会出现重复项，时间复杂度仍然是 O(n^2)。
O(n) 的随机化解法非常简单；采用支持 O(1) 滑动窗口的哈希函数（例如 Rabin fingerprint），先对字符串1 进行哈希，再对字符串2 进行哈希，然后移动哈希函数1 的窗口，并检查是否有碰撞。
如果我们想象最坏的情况是扫描两个 DNA串，则可能发生碰撞的概率会增加，这可能会退化成类似于 O(n^(1+e)) 的复杂度（这只是猜测）。
最后，还有一种确定性的 O(nlogn) 解法，但外面有一个非常大的常数。基本思路是将两个字符串卷积起来。卷积的最大值就是两个字符串是否旋转的差异，使用 O(n) 检查即可确认。好处是如果有两个相等的最大值，则它们都是有效解。您可以用两个快速傅里叶变换和一个点乘以及一个反向快速傅里叶变换进行卷积，所需时间为：nlogn + nlogn + n + nlogn + n == O(nlogn)。
由于不能填充零位，并且无法保证字符串长度为2^n，因此FFT将不是快速傅里叶变换，而是较慢的变换，仍然是O(nlogn)，但常数比CT算法要大得多。
总之，我绝对、100%地相信这里有一种确定性的 O(n) 解决方案，但我找不到它。
这是一个时间复杂度为O(n)且在原地执行的算法。它使用<运算符来比较字符串元素。当然这不是我的算法，我从这里找到了它（该网站为波兰语，我曾经在过去偶然发现过它，但现在无法用英文找到类似的内容，所以只能分享这个了 :))。
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 is_rotation(char* s1, char* s2)
{
char *tmp1;
char *tmp2;
char *ref2;
assert(s1 && s2);
if ((s1 == s2) || (strcmp(s1, s2) == 0))
return (1);
if (strlen(s1) != strlen(s2))
return (0);
while (*s2)
{
tmp1 = s1;
if ((ref2 = strchr(s2, *s1)) == NULL)
return (0);
tmp2 = ref2;
while (*tmp1 && (*tmp1 == *tmp2))
{
++tmp1;
++tmp2;
if (*tmp2 == '\0')
tmp2 = s2;
}
if (*tmp1 == '\0')
return (1);
else
++s2;
}
return (0);
}
我猜最好用Java来做这件事情：
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}
或者更好的方法是使用index函数而不是正则表达式：
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
/\Q$string2/中忘记了\Q。 - Kragen Javier Sitaker\Q会转义 $string2 中的任何特殊字符。如果不使用它，. 将被视为任意一个1个字符的字符串的旋转。 - jackrabbit