Suffix array

In short: A suffix array is a sorted list of all suffixes of a text. With it any substring can be found by binary search.

In more detail: For the text banana the suffixes are banana, anana, nana, ana, na, a. Only their start positions are stored in alphabetical order: [5, 3, 1, 0, 4, 2].

In Depth

• Search: A pattern of length m is found by binary search over the suffixes, in O(m log n).
• Construction: Naively by sorting in O(n² log n). Good algorithms (SA-IS, prefix doubling) reach O(n) to O(n log n).
• Versus suffix trees: Slightly slower but far less memory.
• LCP array extra: Stores the common prefix length of neighbouring suffixes and enables more queries, such as the longest repeated substring.
• Use: Bioinformatics (genome search), the Burrows-Wheeler transform in bzip2, plagiarism detection, full-text indexes.
• Comparison: For repeated searches in the same text the index pays off. A one-off search is done by KMP or Boyer-Moore.

See also: Inverted index