Suffix Arrays

LA home
  Suffix array
  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:

Try: Wolloomooloo


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.

© L. Allison   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Tuesday, 28-Mar-2017 09:44:55 EDT.

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