string - "Lexicographically minimal string rotation"与 "finding the lexicographical min suffix"相同吗？

Question

很多人可能都知道字典最小字符串旋转的问题。解决方案如下:How to find the number of the lexicographically minimal string rotation?

---

但我并不是要重复的解决方案。相反，我想问另一个相关问题:是否与查找字典最小后缀的问题相同？

例如，我们有字符串bbaaccaadd。

按字典顺序排列的最小字符串旋转将是“aaccaaddbb”。

要找到它，我是否可以只找到bbaaccaadd的最小后缀，即aaccaadd，并在末尾附加head 2“bb”？

---

这两个问题是否相同？

Answer 1

To find it, can I just find the minimal suffix of bbaaccaadd, which is aaccaadd and append the head 2 "bb" at the end?

这并不总是会产生正确的最小旋转。以 S = baa 为例。那么最小后缀是a，但是最小旋转是aab，不是ab。

但是，我们可以证明

min_rotation(S) = min_suffix(S + S + '∞') 

其中 '∞' 是一个比 S 中的每个字符都大的字符。

Are these two problems identical?

显然不完全是，但它们的关系非常密切。正如我们所见，我们可以使用 min-suffix 通过简单的归约来解决 min-rotation。我还没有看到反向减少，但也许有类似的。正如 David 所指出的，如果我们将负无穷大附加到字符串 S，则该字符串的第二最小旋转对应于它的最小后缀。另外，Booth's最小旋转 jar 的算法 easily be adapted解决最小后缀。