0
$\begingroup$

Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?

$\endgroup$

2 Answers 2

1
$\begingroup$

Sure: the longest stored suffix is the string itself.

In a suffix array, it's particularly easy to find: scan the array for starting index $1$ -- the suffix starting at the first character is, quite obviously, the string itself.

$\endgroup$
1
$\begingroup$

Understanding the definition of a suffix array will come in handy here.

http://en.wikipedia.org/wiki/Suffix_array

Suffix Array for the string attcatg$.

enter image description here

So like Raphael Suggested either look for the index 1 string attcatg$ or look for the longest string in that array which is the same if it doesn't store indices but it should store indices as per definition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.