如何查找与给定后缀数组匹配的某个字符串？

Question

我有一个后缀数组。如何获取一个字符串，使得该后缀数组等于给定的数组？

例如，我有这个数组：[7, 6, 4, 2, 1, 5, 3]。那么字符串banana$对我来说很好，因为get_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3]。

- David

---

你不能从后缀数组中恢复一个字符串。同时，“bapapa$”也有相同的数组。 - Ami Tavory

@AmiTavory，我想要恢复任何具有相同后缀数组的字符串。 - David

也许你应该重新构思一下标题。 - Ami Tavory

@AmiTavory，我已经编辑好了。 - David

好的，谢谢。现在好多了。 - Ami Tavory

Answer 1

你可以根据约束条件建立一个有向图，然后运行拓扑排序，并根据结果顺序为节点分配字母。

首先为未知字母构建节点，每个字母一个（除了$）。

第一个条目将始终是数组的长度，因为它是$。这给我们没有信息。

但是，接下来的条目每个都给出了限制条件。

例如，由于第二个条目是数组长度减一，因此它不能大于任何其他字母。因此，从此节点到其他所有节点都要放置一条边。 然而，如果它是数组长度减二，则会有一个比它小的字母，但它将小于所有其他字母。您可以从后缀数组中找到这个较小的元素，并从它到最后一个字母，以及从最后一个字母到所有其他字母等放置节点。

- Ami Tavory