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

4. Suffix arrays

Thomas Mailund1 
(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 ...

Get String Algorithms in C: Efficient Text Representation and Search now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.