arrays - 如何找到与给定后缀数组匹配的字符串？

Question

我有一个后缀数组。如何获取一个字符串，哪个后缀数组将等于给定数组？

例如。让我有这个数组：[7, 6, 4, 2, 1, 5, 3]。然后字符串banana$对我有好处，因为get_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3].

Answer 1

您可以从约束构建有向图，然后运行拓扑排序，并根据结果顺序为节点分配字母。

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

第一个条目将始终是数组的长度，因为它是$. 这没有给我们任何东西。

但是，以下条目都给了我们限制。

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