如何找到字典序最小的字符串转数？ [英] How to find the number of the lexicographically minimal string rotation?

问题描述

如何找到字典序最小的字符串转多少？

例如：

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.

这篇关于如何找到字典序最小的字符串转数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！