string - 如何找到字典序最小的字符串旋转数？

Question

如何找到 lexicographically minimal string rotation 的数量？

例如:

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

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

Answer 1

简单——只需确定字符串的最小周期。一个以最小周期 K 为周期的字符串将产生完全相同的(因此在字典序上相等)字符串完全相同 N/K 不同的旋转，所以无论字典序最小值是什么，它'将是 N/K 不同旋转的结果。