Suffix Arrays

LA home
Computing
Algorithms
 Glossary
 Strings
  Suffix array
  BWT
  Factors
  Suffix tree
  Suffix A.

Given a string, S[1..n], of length n, S[1..i] is a prefix of S, and S[i..n] is a suffix of S, for 1<=i<=n; a substring of S is a prefix of a suffix, and v.v.. In some situations the empty string may also be considered to be a prefix/suffix of S.

Change the Text txt=... in the HTML FORM below, and click on `go'; experiment with different text strings. For a short string, the demo. sorts the suffices by (i) a (very) dumb method, (ii) the suffix array algorithm. For a long string it only runs the suffix array algorithm:

txt=
Try: Wolloomooloo

References

U. Manber, G. Myers. Suffix arrays: a new method for on-line string searches. SIAM J. Comput., 22(5), pp.935-948, Oct 1993.
 
There has been quite a flurry of research activity since 2003.
www:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Sunday, 21-Oct-2018 11:34:48 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.