Suffix Arrays

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:

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.