Geek Answers Handbook

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

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

For example:

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

I tried Duval algorithm, it works for a very long time. The length of the string is 100,000,000 characters.

+7
string algorithm circular-buffer
source share
1 answer

Easy - just define the minimum row period. A line periodic over the minimum period K will produce the same (and therefore lexicographically equal) lines for exactly N/K different rotations, therefore, whatever the lexicographic minimum, this will be the result of N/K different rotations.

+4
source share

More articles:


All Articles