当字符串相当于旋转时

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)