当弦等于旋转时

Question

我有很多弦。就我而言，如果一个字符串是另一个字符串的旋转，则两个字符串是等价的（例如，“1234”相当于“3412”）。在

在Python中，什么是一种高效的方法来处理每一个字符串（直到循环）？在

我想要的东西的天真实现可能看起来像：

class DuplicateException(Exception): pass
seen = set()
for s in my_strings:
  try:
    s2 = s+s
    for t in seen:

      # Slick method I picked up here in SO
      # for checking whether one string is
      # a rotation of another
      if len(s) == len(t) and t in s2:
        raise DuplicateException()

    seen.add(s)
    process(s)
  except DuplicateException: pass

Answer 1

选择一种规范的方式来表示一类旋转的字符串（例如，在所有可能的字符串旋转中，字典上最少的旋转），并且只使用规范表示（规范化）。在

例如：

def canonicalize(s):
    return min(s[i:]+s[:i] for i in xrange(len(s)))

canonical_strings = {canonicalize(s) for s in my_strings}
for cs in canonical_strings:
    process(cs)

Answer 2

也许将你的string旋转到一个特定的值，例如最小的可能旋转，比那些最小的旋转是唯一的，并且可以很容易地放入一个集合中。在

下面是一个示例实现，“rotate_to_minimum”可能会得到改进。在

my_strings = ['1234', '123', '2341', '4312', '312', '56', '65', '1236']

def rotate_to_smallest(x):
    smallest = x
    for i in xrange(1, len(x)):
        rotation = x[i :] + x[: i]
        if rotation < smallest:
            smallest = rotation
    return smallest

def unique_rotations(my_strings):
    uniques = set(())
    for s in my_strings:
        smallest_rotation = rotate_to_smallest(s)
        if smallest_rotation not in uniques:
            uniques.add(smallest_rotation)
    return uniques

结果：

^{pr2}$