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
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.