The Suffix Binary Search Tree
Rob Irving, University of Glasgow
Suffix trees and suffix arrays are well-known as data structures
that represent the set of all suffixes of a given string, and
thereby facilitate the efficient solution of problems such as
substring searching, finding repeated and common substrings, etc.
In this talk, we describe how binary search trees, when
supplemented with appropriate additional information, can
compete, both in theoretical terms and in practice, with suffix
trees and suffix arrays. This is joint work with Lorna Love.