These comprise a number of Ada 95 packages that provide for construction and use of suffix arrays [1]. In each case, the suffix array is built using a suffix binary search tree - see [2, 3]. The four versions depend on whether the tree is in its standard version or its refined version (see [2]), and whether it is represented using dynamically created nodes or using an array of nodes. The refined versions are faster, but use a little more space than the standard versions. However the latter provide more flexibility - see operations list below. The array versions are more space-economical, and just as fast, as those that use dynamic storage.

The procedures provided by the packages are summarised as follows. (Further details can be found in the header comments in the package specifications.)

• a procedure that builds a suffix array for a given string
• a procedure that builds a generalised suffix array for two given strings
• (in the standard versions only) a procedure that builds a partial suffix array for a given string, containing only those suffixes beginning on a ‘word boundary’
• a procedure that searches the suffix array, representing a given string, for a target string X and returns a position (if any) where X occurs
• a procedure that searches the suffix array, representing a given string, for target string X, and returns a list of all of the positions where X occurs
• a function that searches the suffix array, representing a given string, for a target string X, and returns the number of occurrences of X
• a procedure that traverses a suffix array, representing a given string, to find an occurrence of a longest repeated substring
• a procedure that traverses a generalised suffix array, representing two given strings, and returns an occurrence of a longest common substring

The demo programs have a simple text-based interface. They should be run from a command line with one or two file names as parameters. With a single file parameter, they construct the suffix array for the string contained in that file (replacing new-lines by blanks in a text file). They then find a longest repeated substring, and offer the user the option to input a sequence of search strings, reporting the number of occurrences in each case. With two files as parameters, they construct the generalised suffix array for these two strings and find a longest common substring.

The src folder contains the source code, written in Ada 95. It consists of the following:

• .ads and .adb files: a package specification and body for each of the four suffix array implementations described above
• char_set_package.ads, char_set_package.adb: package specification and body for a set of characters (used to obtain a separator)
• integer_list_package.ads, integer_list_package.adb: package specification and body for a list of integers (used to hold a list of positions in a string)

These packages are portable, and may be compiled with any Ada 95 compiler.

The bin folder contains executable versions of demonstration programs for Windows and Unix (PC x86 and Sparc Solaris)

• executables of the form demo.exe for Windows
• executables of the form demo.x86 for Unix on PC architecture
• executables of the form demo.sparc for Unix on Sparc architecture

DISCLAIMER: this software is not supported, and although it has been subjected to extensive testing, the authors cannot take responsibility for any loss etc. resulting from errors or unexpected behaviour.

Copies of the source may be made freely for private study or educational use, provided that the program headers acknowledging the authors are retained.

1. U. Manber & E.W. Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal of Computing 22 (1993), 935-948.