How to detect palindrome cycle length in a string?

Question

Suppose a string is like this "abaabaabaabaaba", the palindrome cycle here is 3, because you can find the string aba at every 3rd position and you can augment the palindrome by concatenating any number of "aba"s to the string.

I think it's possible to detect this efficiently using Manacher's Algorithm but how?

Answer 1

You can find it easily by searching the string S in S+S. The first index you find is the cycle number you want (may be the entire string). In python it would be something like:

In [1]: s = "abaabaabaabaaba"

In [2]: print (s+s).index(s, 1)
3

The 1 is there to ignore the index 0, that would be a trivial match.