Suffix array: Difference between revisions

Revision as of 22:29, 20 December 2004

Revision as of 03:56, 21 April 2005

Line 1:

A suffix array (invented by [[Gene Myers]] and [[Udi Manber]]) is an indexing structure for locating substrings in a larger string. Originally developed to reduce memory consumption compared to a [[suffix tree]], this structure began the trend towards compressed suffix arrays and [[BWT]]-based compressed full-text indices.

The ''kth 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.