如何找到字典序最小的字符串转多少?
例如:
S = abab, N = 2
S = abca, N = 1
S = aaaa, N = 4
我试过杜瓦尔的算法,它的工作原理很长。 100000000字符的字符串长度。
I tried Duval's algorithm, it works very long. The string length of 100000000 characters.
容易 - 只需确定字符串的最短期限。一个字符串,它是定期在最短的时间 K
会产生相同的(因此字典顺序相同)字符串完全 N / K
不同的旋转,因此无论词典最小值是,这将是对 N / K
旋转不同的结果。
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.