Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation.

Idea

  1. to handle rotation, we just cocatinate the string again. But how do we handle to problem of fixed size n?
  2. If we forget about the fixed size n requirement, we can just construct a suffix array, and the first entry will be lex smallest.
  3. Now if we look at the first entry in the suffix array with length at least n, we know that a rotation must be its prefix. Moreoever, all rotations are covered in our suffix array already
  4. Now consider the first and second such suffixes, we know that lexigraphically, the n-size of first prefix <= n-size of the second prefix. Therefore, the rotation starting at i <= the rotation staring at i+1
  5. Apply such arguments to all rotations appearing in the suffix array, we know the first entry has the lex smallest rotation