2 
s = raw_input()
n = len(s)
el = []
z = n - 1
while z >= 0:
    x = s[z:] + s[:z]
    z = z - 1
    el.append(x)
print max(el)

代码运行良好，但效率非常低。
有没有更省时的方法来解决问题？

4

1 回答 1

0

方法

您可以使用后缀数组在线性时间内解决此问题。给定输入字符串s，构造双倍字符串ss。使用线性时间算法构造 的后缀数组ss。suffix 数组ss按字典顺序保存 suffices 的索引。最后，向后扫描后缀数组，跳过ss. 从 的前半部分开始的字典顺序最大的后缀ss可以被修剪为s.

该问题与此处描述的问题类似，只是该问题是关于字典顺序最小的旋转，而您想要字典顺序最大的旋转。

执行

上面链接的文章提到了一些可用于后缀数组构造的算法。我不会在这里给出这部分的显式构造，但是对于 Python 实现，参见例如这篇文章。

因此，假设您有一些后缀数组算法的实现create_suffix_array(s: str) -> [int]，create_suffix_array(s)以便按字典顺序返回 suffices 的索引序列，然后您可以将算法应用于您的问题，如下所示：

def rotate(s: str, n: int) -> str:
  return s[n:] + s[:n]

def solve(s: str) -> str:
  indices: [int] = create_suffix_array(s + s)

  is_first_half = lambda i: i < len(s)

  best_index = next(filter(is_first_half, reversed(indices)))

  return rotate(s, best_index)

算法的正确性

让s是一个长度的字符串n。让是从 的前半部分开始i的按字典顺序排列的最大后缀的索引。它的后缀由is定义。ssssssis[i,n-1]s

考虑任何j. [0,n-1]那么它的后缀ss定义为j不能大于s[i,n-1]s。所以s[j,n-1]s <= s[i,n-1]s。然后，这些后缀的任何两个大小相等的前缀都具有相同的顺序。特别是，s[j,n-1]s[0,j-1] <= s[i,n-1]s[0,i-1], 因为两者都是n-size 的前缀，这两者就足够了。

因此，s[i,n-1]s[0,i-1]是 的字典序上最大的旋转s。

于 2020-11-21T00:19:49.947 回答