(data structure)
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 ...)
array.
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.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 7 December 2007.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "inverse suffix array", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 December 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/inverseSuffixArray.html