Count the number of cyclic words in an input Cyclic Words


  Problem Statement
  
  We can think of a cyclic word as a word written in a circle. To
  represent a cyclic word, we choose an arbitrary starting position and
  read the characters in clockwise order. So, "picture" and "turepic"
  are representations for the same cyclic word.
  
  You are given a String[] words, each element of which is a
  representation of a cyclic word. Return the number of different cyclic
  words that are represented.


Fastest wins (Big O, where n = number of chars in a string)
Python

Here's my solution. I think it might still be O(n2), but I think the average case is much better than that.

Basically it works by normalizing each string so that any rotation will have the same form. For example:

'amazing' -&gt; 'mazinga'
'mazinga' -&gt; 'mazinga'
'azingam' -&gt; 'mazinga'
'zingama' -&gt; 'mazinga'
'ingamaz' -&gt; 'mazinga'
'ngamazi' -&gt; 'mazinga'
'gamazin' -&gt; 'mazinga'


The normalization is done by looking for the minimum character (by char code), and rotating the string so that character is in the last position. If that character occurs more than once, then the characters after each occurrence are used. This gives each cyclic word a canonical representation, that can be used as a key in a map.

The normalization is n2 in the worst case (where every character in the string is the same, e.g. aaaaaa), but most of the time there's only going to be a few occurrences, and the running time will be closer to n.

On my laptop (dual core Intel Atom @ 1.66GHz and 1GB of ram), running this on /usr/share/dict/words (234,937 words with an average length of 9.5 characters) takes about 7.6 seconds.

#!/usr/bin/python

import sys

def normalize(string):
   # the minimum character in the string
   c = min(string) # O(n) operation
   indices = [] # here we will store all the indices where c occurs
   i = -1       # initialize the search index
   while True: # finding all indexes where c occurs is again O(n)
      i = string.find(c, i+1)
      if i == -1:
         break
      else:
         indices.append(i)
   if len(indices) == 1: # if it only occurs once, then we're done
      i = indices[0]
      return string[i:] + string[:i]
   else:
      i = map(lambda x:(x,x), indices)
      for _ in range(len(string)):                       # go over the whole string O(n)
         i = map(lambda x:((x[0]+1)%len(string), x[1]), i)  # increment the indexes that walk along  O(m)
         c = min(map(lambda x: string[x[0]], i))    # get min character from current indexes         O(m)
         i = filter(lambda x: string[x[0]] == c, i) # keep only the indexes that have that character O(m)
         # if there's only one index left after filtering, we're done
         if len(i) == 1:
            break
      # either there are multiple identical runs, or
      # we found the unique best run, in either case, we start the string from that
      # index
      i = i[0][0]
      return string[i:] + string[:i]

def main(filename):
   cyclic_words = set()
   with open(filename) as words:
      for word in words.readlines():
         cyclic_words.add(normalize(word[:-1])) # normalize without the trailing newline
   print len(cyclic_words)

if __name__ == '__main__':
   if len(sys.argv) &gt; 1:
      main(sys.argv[1])
   else:
      main("/dev/stdin")