这是一个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);
}

将每个字符作为振幅，并对其进行离散傅里叶变换。如果它们仅因旋转而不同，则频谱将在舍入误差范围内相同。当然，这是低效的，除非长度是2的幂，所以你可以做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)解，但我不知道我能不能找到它。

编辑:如果你发现了，公认的答案显然比这个更优雅、更有效。我把这个答案留给了我所做的，如果我没有想到将原始字符串加倍的话。

我就用蛮力。首先检查长度，然后尝试每一个可能的旋转偏移。如果没有，则返回false;如果有，则立即返回true。

没有特别的连接需要——只需使用指针(C)或索引(Java)，并在每个字符串中使用一个指针——从一个字符串的开头开始，在第二个字符串中使用当前的候选旋转偏移量，并在必要的地方进行换行。检查字符串中每个点的字符是否相等。如果你到达了第一个字符串的末尾，你就完成了。

它可能同样容易连接-尽管效率可能较低，至少在Java中是这样。

首先，确保两根弦的长度相同。然后在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);
}