今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
其他回答
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
反转其中一个字符串。取两者的FFT(将它们视为简单的整数序列)。将结果逐点相乘。使用反FFT转换回来。如果弦是彼此旋转的，那么结果将只有一个峰值——峰值的位置将由它们相对于彼此旋转的多少来指示。
Opera的简单指针旋转技巧是有效的，但是在运行时最糟糕的情况下效率极低。简单地想象一个有许多长重复字符的字符串，例如:
S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2 S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1
从计算角度来看，“循环直到出现不匹配，然后再加1，再试一次”是一种可怕的方法。
为了证明你可以毫不费力地在C语言中使用串联方法，下面是我的解决方案:
int isRotation(const char* s1, const char* s2) {
assert(s1 && s2);
size_t s1Len = strlen(s1);
if (s1Len != strlen(s2)) return 0;
char s1SelfConcat[ 2 * s1Len + 1 ];
sprintf(s1SelfConcat, "%s%s", s1, s1);
return (strstr(s1SelfConcat, s2) ? 1 : 0);
}
这在运行时间上是线性的，以开销中O(n)内存使用为代价。
(请注意，strstr()的实现是特定于平台的，但如果特别脑死亡，总是可以用更快的替代方案替代，如Boyer-Moore算法)
这是一个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;
}
首先确保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);
}
