| Invented by | Udi Manber, Gene Myers (1990) | |
| Idea: |
- sort all \(n\) suffixes of the text and store their starting positions in lexicographic order
- suffixes that start with the same pattern land next to each other, so the answer to a search is always one block of rows — found by binary search
- the companion LCP array stores, for each row, how many leading characters it shares with the row above; with it the array carries the same information as a suffix tree
|
| Advantages: |
- several times smaller than a suffix tree over the same text: the array is just one integer per character, with no pointers and no per-node overhead
- independent of the alphabet size: only comparisons of symbols are needed, where a suffix tree needs a child lookup per node
|
| Variations: |
- there are many suffix array construction algorithms, from the trivial \(O(n^2\log n)\) to optimal \(O(n)\); this visualization shows prefix doubling, which takes \(O(n\log n)\)
- the array can be used with or without the LCP array; the trade-off is more space against faster operations
|
| Disadvantages: |
- the search is a binary search, not a walk down a trie, so it costs a \(\log n\) factor a suffix tree does not pay; matching statistics and other suffix-link algorithms need the LCP array plus extra structure to imitate the tree
|