今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
我喜欢检查s2是否是s1与s1连接的子字符串的答案。
我想要添加一个不会失去其优雅的优化。
你可以使用连接视图代替连接字符串(我不知道其他语言，但c++ Boost。Range提供这样的视图)。
由于检查一个字符串是否是另一个字符串的子字符串具有线性平均复杂度(最坏情况的复杂度是二次的)，这种优化应该平均提高2倍的速度。
其他回答
C#:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
这是一个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;
}
编辑:如果你发现了，公认的答案显然比这个更优雅、更有效。我把这个答案留给了我所做的，如果我没有想到将原始字符串加倍的话。
我就用蛮力。首先检查长度，然后尝试每一个可能的旋转偏移。如果没有，则返回false;如果有，则立即返回true。
没有特别的连接需要——只需使用指针(C)或索引(Java)，并在每个字符串中使用一个指针——从一个字符串的开头开始，在第二个字符串中使用当前的候选旋转偏移量，并在必要的地方进行换行。检查字符串中每个点的字符是否相等。如果你到达了第一个字符串的末尾，你就完成了。
它可能同样容易连接-尽管效率可能较低，至少在Java中是这样。
哇,哇……为什么每个人都对O(n²)的答案如此兴奋?我相信我们可以做得更好。上面的答案包括O(n)循环中的O(n)操作(substring/indexOf调用)。即使有更高效的搜索算法;比如Boyer-Moore或KMP，最坏情况仍然是O(n^2)有重复。
O(n)随机化的答案很简单;取一个支持O(1)滑动窗口的哈希值(如Rabin指纹);哈希字符串1，然后哈希字符串2，然后继续围绕字符串移动哈希1的窗口，看看哈希函数是否冲突。
如果我们想象最坏的情况是“扫描两条DNA链”，那么碰撞的概率就会上升，这可能退化为O(n^(1+e))或其他(只是猜测)。
最后，有一个确定的O(nlogn)解，它有一个非常大的常数。基本上，就是对两个弦进行卷积。卷积的最大值将是旋转差(如果它们被旋转);O(n)检查确认。好处是如果有两个相等的最大值，那么它们也是有效解。你可以用两个FFT进行卷积一个点积，一个iFFT，所以nlogn + nlogn + n + nlogn + n = O(nlogn)
因为你不能用0填充，你不能保证字符串的长度是2^n, fft不会是最快的;它们会变慢，仍然是O(nlogn)，但比CT算法大得多。
说了这么多，我绝对，100%肯定这里有一个确定的O(n)解，但我不知道我能不能找到它。
我喜欢检查s2是否是s1与s1连接的子字符串的答案。
我想要添加一个不会失去其优雅的优化。
你可以使用连接视图代替连接字符串(我不知道其他语言，但c++ Boost。Range提供这样的视图)。
由于检查一个字符串是否是另一个字符串的子字符串具有线性平均复杂度(最坏情况的复杂度是二次的)，这种优化应该平均提高2倍的速度。
