5.4.2004

We describe an efficient data structure for searching a set of strings of arbitrary length. Search and update operations for a string of length d can be performed in simultaneous time O(log n + d) and space O(n) where n is the number of strings. The best up to now known data structures required a superlinear space for the same time bound. This data structure could be of particular interest for the case of sets containing long strings. We conclude with some experimental results and some benchmark comparisons with other search methods.