python - 检查一个列表是否是另一个与重复项一起使用的列表的轮换

Question

我有这个函数来确定一个列表是否是另一个列表的轮换:

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

例如

>>> 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)时间内完成吗？

Answer 1

下面的元算法将解决它。

• 构建 a 的串联，例如，a = [3,1,2,3,4] => aa = [3 ,1,2,3,4,3,1,2,3,4].

• 运行任何字符串匹配算法的字符串适配，例如，Boyer Moore在 aa 中查找 b。

---

我首先尝试的一个特别简单的实现是使用 Rabin Karp作为底层算法。在这种情况下，你会

• 计算Rabin Fingerprint对于 b

• 计算aa[: len(b)], aa[1: len(b) + 1], ...的Rabin指纹, ...,并仅在指纹匹配时比较列表

注意

• 可以非常高效地迭代计算滑动窗口的 Rabin 指纹(在 Rabin-Karp 链接中了解它)

• 如果你的列表是整数，你实际上比字符串更容易，因为你不需要考虑一个字母的数字哈希值是什么

-