Definition: For each position in a string, the inverse suffix array has its index in the string's suffix array.
Formal Definition: Given a suffix array, sa, and the corresponding inverse suffix array, isa, isa[i] = j iff sa[j] = i.
Generalization (I am a kind of ...)
See also suffix array.
Note: Consider the string "good". In one-based indexing, the suffix array is [4, 1, 3, 2]. The inverse suffix array is [2, 4, 3, 1].
Many algorithms to build suffix arrays use an inverse suffix array. A suffix array can be built from the inverse suffix array in linear time. An inverse suffix array can be turned into a suffix array in place in linear time, too.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 7 December 2007.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "inverse suffix array", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 7 December 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/inverseSuffixArray.html