CODEWITHSUNDEEP
stringalgorithmcircular-buffer
user3164559
user3164559

Reputation: 287

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

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.

Upvotes: 7

Views: 2517

Answers (1)

Sneftel
Sneftel

Reputation: 41503

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.

Upvotes: 4

Related Questions