A sorted array of all the starting positions of a string's suffixes, giving much of a suffix tree's search power in a smaller and simpler structure, often paired with a longest-common-prefix array for substring queries.
Facts
Core PrincipleStores all suffixes of a string as a sorted array of their starting positions, giving many of a suffix tree's search abilities in a smaller and simpler structure. 1 Connections
Sources
1. Wikipedia: Suffix Array
Wikimedia FoundationLead section, second sentence
Suffix arrays were introduced by Manber & Myers (1990) as a simple, space efficient alternative to suffix trees.
Lead section, first sentence
a suffix array is a sorted array of all suffixes of a string.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.