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   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Friday, 25-Jul-2014 20:36:37 EST.

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