0

考虑一个长度为 n (1 <= n <= 100000) 的字符串。确定其最小字典旋转。例如，字符串“alabala”的旋转是：

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

and the smallest among them is “aalabal”.

这个问题已经在 Stack 上被问过，但我正在问它，因为没有明确的解决方案可用。到目前为止，我取得了以下进展。
1.取S，concat with reverse(S)..let P=S+reverse(S)
2.构造上述字符串P的后缀数组

现在我的问题是如果我选择后缀数组中的第一个字符串size> strlen(S)那么这个字符串大小strlen(S)的前缀将是给定字符串 S 的最小旋转。

我的结论正确吗？

4

1 回答 1

0

不，一般来说这是错误的（如果我理解正确的话）。当然，它适用于您的回文输入。

请参阅 python 解释器的以下输出，其中输入字符串包括'alabala'和'alabatta'。（输出添加了一些空格和换行符。）在第二部分中，第一个比 S 长的后缀的前部是不允许的，即不是 S 的旋转。有关有效的方法，请参见第三部分。

>>> s = 'alabala'; p = s + ''.join(reversed(s))
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aalabala', 'abala', 'abalaalabala', 'ala', 'alaalabala',
 'alabala', 'alabalaalabala', 'bala', 'balaalabala', 'la',
 'laalabala', 'labala', 'labalaalabala']

>>> s = 'alabatta'; p = s + ''.join(reversed(s))
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aattabala', 'abala', 'abattaattabala', 'ala', 'alabattaattabala',
 'attaattabala', 'attabala', 'bala', 'battaattabala', 'la',
 'labattaattabala', 'taattabala', 'tabala', 'ttaattabala', 'ttabala']

>>> s = 'alabatta'; p = s + s
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aalabatta', 'abatta', 'abattaalabatta', 'alabatta', 
 'alabattaalabatta', 'atta', 'attaalabatta', 'batta', 'battaalabatta',
 'labatta', 'labattaalabatta', 'ta', 'taalabatta', 'tta', 'ttaalabatta']
于 2012-11-03T06:31:27.573 回答