Suffix array: Difference between revisions

Revision as of 19:42, 9 December 2005

Revision as of 01:40, 10 March 2006

Line 1:

A '''suffix array''' is an [[index (information technology)|index structure]] for locating [[substring]]s in a larger [[string (computer science)|string]]. It is an array of indexes giving the [[lexicographical order]] of the [[suffix]]es. A suffix array for a string ''S'' of length ''n'' can be built in Θ(''n'') time, and lets you find all ''occ'' occurrences of a pattern ''P'' of length ''m'' in ''S'' in O(''m'' + log ''n'' + occ) time. Suffix arrays wherewere originally developed by [[Gene Myers]] and [[Udi Manber]] to reduce memory consumption compared to a [[suffix tree]]. This began the trend towards compressed suffix arrays and [[BWT]]-based compressed full-text indices.

The ''k''th suffix of a string ''S'' is ''S'' with the first ''k''-1 characters removed, for some starting position ''k''. A string of ''n'' characters has ''n'' suffixes, denoted by their starting positions 1..''n''. For instance, the string "abracadabra" has the following suffixes: