今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
将每个字符作为振幅，并对其进行离散傅里叶变换。如果它们仅因旋转而不同，则频谱将在舍入误差范围内相同。当然，这是低效的，除非长度是2的幂，所以你可以做FFT:-)
其他回答
由于其他人已经提交了二次最坏情况时间复杂度解决方案，我将添加一个线性解决方案(基于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;
}
工作示例
反转其中一个字符串。取两者的FFT(将它们视为简单的整数序列)。将结果逐点相乘。使用反FFT转换回来。如果弦是彼此旋转的，那么结果将只有一个峰值——峰值的位置将由它们相对于彼此旋转的多少来指示。
哇,哇……为什么每个人都对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)解，但我不知道我能不能找到它。
当然，更好的答案应该是，“嗯，我会问stackoverflow社区，可能会在5分钟内得到至少4个非常好的答案”。有头脑是很好的，但我更看重那些知道如何与他人合作找到解决方案的人。
下面是一个使用正则表达式的例子，只是为了好玩:
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())
);
}
