如何找到按字典顺序排列的最小字符串旋转数？

Question

如何找到按字典顺序排列的最小字符串旋转次数？

例如:

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

我试过Duval的算法,它的工作时间很长.字符串长度为100000000个字符.

Answer 1

很简单——只需确定字符串的最小周期即可。在最小周期内具有周期性的字符串K将针对完全不同的旋转产生相同（因此字典顺序相等）的字符串，因此无论字典顺序最小值是多少，它都将是不同旋转N/K的结果。N/K