Problem 37: Cyclic Equivalence

Two words are cyclically equivalent if one is a conjugate (rotation) of the other. Testing their equivalence appears in some string matching questions but also in graph algorithms, for example, for checking the isomorphism of directed labelled graphs, in which the test applies to graph cycles.

The following algorithm tests cyclic equivalence using the alphabet ordering.

CyclicEquivalence$(u,v \textrm{ non-empty words of length } n)$

    \begin{algorithmic}
  \STATE $(x,i,y,j) \leftarrow (uu,0,vv,0)$
  \WHILE{$i\lt n \mbox{ and } j\lt n$}
    \STATE $k \leftarrow 0$
    \WHILE{$k\lt n \mbox{ and } x[i+k] = y[j+k]$}
      \STATE $k \leftarrow k+1$
    \ENDWHILE
    \IF{$k=n$}
      \RETURN{\True} 
    \ENDIF
    \IF{$x[i+k] \gt y[j+k]$}
      \STATE $i \leftarrow i+k+1$
    \ELSE
      \STATE $j \leftarrow j+k+1$
    \ENDIF
  \ENDWHILE
  \RETURN{\False}
    \end{algorithmic}

Show that Algorithm CyclicEquivalence checks if two words are cyclically equivalent and runs in linear time with constant extra space.

Consider Lyndon conjugates.

When the alphabet has no clear ordering, it is useful to have a solution based on simpler types of symbol comparisons.

How would you test the cyclic equivalence of two strings with no ordering, that is, using only $=$/$\neq$ letter comparisons?

References

M. Crochemore and D. Perrin. Two-way string-matching. J. ACM, 38(3):651-675, 1991.

M. Crochemore and W. Rytter. Squares, cubes, and time-space efficient string searching. Algorithmica, 13(5):405-425, 1995.

Z. Galil and J. I. Seiferas. Time-space-optimal string matching. J. Comput. Syst. Sci., 26(3):280-294, 1983.

Y. Shiloach. A fast equivalence-checking algorithm for circular lists. Inf. Process. Lett., 8(5):236-238, 1979.

125 Problems in Text Algorithms

Example

Problem 37: Cyclic Equivalence

References