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

2018-06-27 11:00:27

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.

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.

链接地址: http://www.djcxy.com/p/76762.html

上一篇: DOM替换元素上的整个样式属性（CSSStyleDeclaration）

下一篇: 如何找到字典上最小字符串旋转的数量？