How can I find a string that matches a given suffix array?
I have an array of suffixes . How to get a string, which suffix array will be equal to a given array?
For example. Suppose I have this array: [7, 6, 4, 2, 1, 5, 3]
. Then the string banana$
is good for me, since get_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3]
.
source to share
You can build a directed graph from the constraints, then run Topological Sort and letter the nodes according to the resulting order.
Start by plotting nodes for the unknown letters, one for each (except $
).
The first entry will always be the length of the array, since it is $
. It gives us nothing.
The following entries, however, give us limitations.
For example, since the second entry is the length of the array minus one, it should not be larger than any of the other letters. So place an edge from this node in each of the others. If, however, it is the length of the array minus two, then there will be less letter than it, but it will be less than all the others. You can find which is this smaller element from the suffix array and place the node from it to the last letter, and from the last letter to all other letters, etc.
source to share