检查一个列表是否是另一个可处理重复项的列表的轮换

我有这个函数来确定一个列表是否是另一个列表的旋转：

def isRotation(a,b):
  if len(a) != len(b):
    return False

  c=b*2
  i=0

  while a[0] != c[i]:
    i+=1

  for x in a:
    if x!= c[i]:
      return False
    i+=1

  return True

e.g.

>>> a = [1,2,3]
>>> b = [2,3,1]
>>> isRotation(a, b)
True

我如何使这项工作与重复项一起工作？例如

a = [3,1,2,3,4]
b = [3,4,3,1,2]

可以在O(n)time?

下面的元算法将解决这个问题。

• 建立一个串联a, e.g., a = [3,1,2,3,4] => aa = [3,1,2,3,4,3,1,2,3,4].

• 运行字符串匹配算法的任何字符串改编，例如，博耶·摩尔 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm找到b in aa.

我首先尝试的一个特别简单的实现是使用拉宾·卡普 https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm作为底层算法。在这方面，你会

• 计算拉宾指纹 https://en.wikipedia.org/wiki/Rabin_fingerprint for b

• 计算拉宾指纹aa[: len(b)], aa[1: len(b) + 1], ..., 仅当指纹匹配时才比较列表

注意

• 滑动窗口的 Rabin 指纹可以非常有效地迭代计算（在 Rabin-Karp 链接中阅读）

• 如果您的列表是整数，那么实际上比字符串要容易一些，因为您不需要考虑字母的数字哈希值是多少

-