From Haoyuep@aol.com Sat Jun 28 16:33:24 2008
Date: Sat, 28 Jun 2008 16:33:15 -0400
From: Dan Hoey <haoyuep@aol.com>
To: "Keith F. Lynch" <kfl@KeithLynch.net>
Subject: Re: Followup

Keith, you wrote:
> Since it doesn't
> matter to the repetition rate where the string begins, I said it might
> as well begin with "A."  That's the only speedup.

I must have been low on oil not to have noticed that this speedup
can be extended to a factor of almost 2N.  You just have to make
sure your string is the canonical representative of the set of its
rotations and reversals.  Starting with A is part of the work of
choosing the lexicographically least as the canonical representative,
but you waste at least half your tests, and probably more like 80-90%.

You can use a "loser table" like in Knuth-Morris-Pratt so that you only
generate strings that are lexicographically least among their sets of
rotations, and then check in linear time that there is no rotation of
their reversal that is lexicographically less.  I don't know if you've
ever used this data structure before, but I can go into it more if the
material on the web isn't clear.  There's a page somewhere out there on
string searching algorithms that describes what's going on, but let me
know if you want help.

Dan