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.
www #ad:

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Monday, 15-Apr-2024 13:15:37 UTC.

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