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.

Georgetown

I don't think you want lexicographically minimal string rotation, but the period of a periodic string. #8348312 – Bumbledom

What do you mean by number of rotation? Does each rotation have a number? What is the number of a rotation? Don't you rather want the total number of rotations (rotationS - in plural)? – Metacarpal

Duval's algorithm works in O(N) with O(1) memory requirement. If this seems to be slow to you, give it up, there won't be anything faster! The program needs at least to read the whole string, which gives the minimum time O(N)! – Metacarpal

What do you call very long ? How did you implement it ? Using what language ? Properly coded and optimized, a linear-time algorithm on 10^8 elements should take a few seconds. – Manton

@Metacarpal O(N) does not mean that there is nothing that could be faster. There could be an another algorithm with O(N) complexity, and 100x faster execution time. – Branks

@Branks only by a constant :) Yes of course I know. The problem of the OP is that he puts huge amount of data into fast algorithm and he just says "it's slow". What can you say to him :) – Metacarpal

@Metacarpal Only the constant what matters in practise, when you compare two algorithm with same complexity:) I know the huge dataset is the problem, I just wanted to point that out O(N) does not mean "fastest":) – Branks

@Branks your comment is only theoretic though. In this case there is really hardly any chance that the OP will find anything faster than the Duval. – Metacarpal

@Metacarpal You misunderstand me, I just wanted to point out your incorrect deduction : O(N) --> fastest – Branks

@Metacarpal I understood you very well but this is only theoretic discussion, as I wrote in my previous comment - not very relevant for OPs case. Look we just cluttered this question with 6 comments about some theoretic discussion, I suggest we do a comment cleanup and delete these comments. – Metacarpal

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.

Sorcerer

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

Why would you need Duval's algorithm? Nothing about determining the number of least permutations requires you to find any of them. – Sorcerer

Then how can I find K? – Georgetown

@user3164559: Well, you said N = 100000000 = 10^8. K must be a divisor of N. N = 10^8 = 2^8 * 5^8 has only 9*9 = 81 divisors. Not counting N itself leaves us with 80 possibilities. So why not simply verify all 80 possible rotations? It should be straightforward to validate each possibility in O(N) time. – Sinusoid