This is an Ada 95 package that provides for construction and use of suffix

trees. The procedures provided by the package are summarised as follows.

(Further details can be found in the header comments in the package specification,

suffix_tree.ads.)

• a procedure that builds a suffix tree for a given string
• Ukkonen's on-line construction algorithm [1] is used

• a procedure that builds a generalised suffix tree for two given strings

• a procedure that searches the suffix tree, representing a given string, for a target string X and returns a position (if any) where X occurs

• a procedure that searches the suffix tree, 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 tree, representing a given string, for a target string X, and returns the number of occurrences of X

• a procedure that traverses a suffix tree, representing a given string, to find an occurrence of a longest repeated substring

• a procedure that traverses a generalised suffix tree, representing two given strings, and returns an occurrence of a longest common substring

• a procedure that destroys a suffix tree

• a procedure that traverses a suffix tree and returns certain statistical information about the tree

The demo program has a simple text-based interface. It should be run from a command line with one or two files as its parameters. With a single file parameter, it constructs the suffix tree for the string contained in that file (replacing new-lines by blanks in a text file), and reports some statistical information on the tree. It then finds a longest repeated substring, and offers the user the option to input a sequence of search strings, reporting the number of occurrences in each case. With two files as parameters, it constructs the generalised suffix tree for these two strings and finds a longest common substring.

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

• suffix_tree.ads, suffix_tree.adb: package specification and body for suffix tree implementation
• char_set_package.ads, char_set_package.adb: package specification and body for a set of characters (used to obtain a dummy terminator/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 a demonstration program for Windows and Unix (PC x86 and Sparc Solaris)

• st_demo.exe for Windows

• st_demo.x86 for Unix on PC architecture

• st_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. E. Ukkonen, On-line construction of suffix trees, Algorithmica 14 (3), 249-260 (1995).