String Algorithms in C: Efficient Text Representation and Search

© Thomas Mailund 2020

T. MailundString Algorithms in Chttps://doi.org/10.1007/978-1-4842-5920-7_4

4. Suffix arrays

Thomas Mailund¹ 

(1)

Aarhus N, Denmark

 

The suffix array data structure is closely tied to the suffix tree, and we have already seen in the previous chapter. The suffix array gives you the lexicographically (alphabetically) sorted order of the suffixes, where each suffix is represented by its index into the string x; see Figure 4-1.

The appeal of the suffix array over suffix trees is its space-efficient and straightforward representation. You can do many of the things you can do with a suffix tree, and with a little extra data and (unfortunately) added complexity, you can simulate suffix trees with suffix arrays. The memory efficiency is ...