NIST

inverse suffix array

(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 1-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


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 16 November 2016.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "inverse suffix array", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 16 November 2016. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/inverseSuffixArray.html