Here's my solution. Nothing as short and sweet as the above code, but I think my algorithm will be much more efficient for long strings. The basic idea is to find all the prime factors of the input length, and use this info to drastically reduce the number of test which need be performed.
E.g. consider an input of length 30, with factors 2, 3, 5. First test to see if a power of 2 works - is the first half of the string equal to the second? If not, then there will be no point in testing any other multiples of two either. For any even power, the first half of the string would have had to be equal to the second.
Alternately if 2 does work as a power, then to test for additional powers it's sufficient to test just the first half of the string, not the whole string. E.g if the max power was 6, the the power of 2 would have shown up first, and the first 15 chars will also have a power of 3. And once you've found powers of 2 and 3, that means that the initial 30-char string consists of 6 repetitions of a single 5-char string. The only remaining untested factor is 5, and so the only remaining thing to test is if that 5-char substring consists of a single char repeated 5 times. Which will fail if the max power was really 6.
Generally my approach will be a little bit slower than Joe's if the input has very high power, meaning it repeats every 1, 2, 3 chars or so. Becaust those are the first types of
patterns Joe tests. But for patterns with longer periods, or patterns with no repetition at all, the factoring method should be a big win, performing far fewer tests.
Primes.java:
PrimeFactors.java:
PowerStrings.java:
And some
JUnit tests which came in handy:
PowerStrings.java:
[ July 21, 2003: Message edited by: Jim Yingst ]