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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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$.
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.
