Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2004 Copyright 2004 Universität Bonn, Institut für Informatik, Abt. V
85256

5.4.2004

An Efficient Data Structure for Searching Strings
Marek Karpinski, Yakov Nekrich
[Download PostScript] [Download PDF]

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.

Last Change: 04/05/04 at 13:49:26
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope