Programming Praxis

One of the pleasures of writing a blog like mine is that I get to learn from my readers just as they learn from me. In a comment on the previous exercise on cyclic equality, reader Maurits pointed to Booth’s algorithm, which I had never previously heard of. Note that Booth’s algorithm is somewhat different than the one we gave in the previous exercise, since Booth’s algorithm relies on an ordering predicate between elements of the cycle while our algorithm relies only on an equality predicate.

Booth’s algorithm creates a canonical rotation of a cycle by putting it in the least possible lexicographic order out of all possible rotations. This is done by a variant of the Knuth-Morris-Pratt string search algorithm. We won’t give the algorithm here, as Wikipedia does a fine job; Booth’s original paper, referenced at Wikipedia, is behind a paywall. Here is Wikipedia’s explanation:

The algorithm uses a modified preprocessing function from the Knuth-Morris-Pratt string search algorithm. The failure function for the string is computed as normal, but the string is rotated during the computation so some indices must be computed more than once as they wrap around. Once all indices of the failure function have been successfully computed without the string rotating again, the minimal lexicographical rotation is known to be found and its starting index is returned. The correctness of the algorithm is somewhat difficult to understand, but it is easy to implement.

Your task is to implement the cyclic equality test of the prior exercise using Booth’s linear-time algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2