How to find the number of the lexicographically minimal string rotation?

Question

How to find the number of lexicographically minimal string rotation?

For example:

S = abab, N = 2
S = abca, N = 1
S = aaaa, N = 4

I tried Duval's algorithm, it works very long. The string length of 100000000 characters.

Answer 1

Easy -- just determine the minimum period of the string. A string which is periodic in minimal period K will produce identical (and hence lexicographically equal) strings for exactly N/K different rotations, so whatever the lexicographic minimum is, it'll be the result of N/K different rotations.