今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
哇,哇……为什么每个人都对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)解，但我不知道我能不能找到它。
其他回答
首先，确保两根弦的长度相同。然后在C中，你可以用一个简单的指针迭代来实现。
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);
}
我在Perl中这样做:
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
首先确保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
在Java中:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
我想最好在Java中这样做:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
在Perl中我会这样做:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}
或者更好的使用index函数而不是regex:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
