如何找到字典顺序最小字符串旋转的编号

Question

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

例如：

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

我尝试了杜瓦尔的算法，它工作很长时间。字符串长度为 100000000 个字符。

Answer 1

简单 -- 只需确定字符串的最小周期。在最小周期内周期性的字符串K将为正好N/K不同的旋转生成相同（因此在词典上相等）的字符串，因此无论词典最小值是多少，它都将是N/K不同旋转的结果。