Suffix array: Difference between revisions

Revision as of 11:41, 5 October 2006

Revision as of 12:42, 19 November 2006

Line 17:

racadabra

If the original string is available, each suffix can be completely specified by the [[zero-based]] or [[one-based]] index of its first character. The suffix array is the array of these indices in lexicographical order. For the string "abracadabra", using [[1-based array|one-based]] indexing, the suffix array is {11,8,1,4,6,9,2,5,7,10,3}, because the suffix "a" begins at the 11th character, "abra" begins at the 8th character, and so forth.

One may also treat the string "abracadabra" as having a twelfth suffix, the empty string (with index 12). But since the empty string will always sort lexicographically before every other suffix, we lose no information by omitting it.