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

Question

我有a suffix array .如何得到一个字符串，哪个后缀数组等于给定的数组？

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

Answer 1

你可以构建一个 directed graph从约束中，然后运行 ​​Topological Sorting , 并根据生成的顺序将字母分配给节点。

首先为未知字母构造节点，每个字母一个($ 除外)。

第一个条目总是数组的长度，因为它是$。这对我们没有任何帮助。

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

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